字符串模板

字符串哈希

模数：

• 比较弱：$1019260817$

• 强得离谱：$212370440130137957$

• （不要问我为啥放这）hash 表模数：$19491001$

const ll mod=/*mod*/,bs=/*base*/;
inline ll gths(int l,int r)
{
return ((hs[r]-hs[l-1]*pow(bs,r-l+1))%mod+mod)%mod;
}
//main
l=str.size();
fru(i,0,l-1)hs[i+1]=(hs[i]*bs+str[i])%mod;

KMP 算法

看毛片

设字符串为 $s$（下标从0开始），$dc$ 为当前模式串 $s$ 判断的下标，$prel_i$ 为 $s[0,i]$ 中最长前缀后缀相等长度，当匹配失败时正好需要会退到下标 $pre_{dc-1}$。

简单来说，匹配过的总长度（在数值上）等于现在匹配的位置。

模板题的代码：

#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>//75760209
#include<ctime>
#include<climits>
#include<random>
#include<algorithm>
#include<unordered_set>
#define fru(i,j,k) for(register int i=j;i<=k;i++)//for_register_up
#define frd(i,j,k) for(register int i=j;i>=k;i--)//for_register_down
#define pc(charx) putchar(charx)
#define finfout(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using ll = long long;
namespace usegetin{
    char c=' ';
    inline ll in()
    {
        ll x=0;bool w=false;
        while(!isdigit(c))
        {
            w|=c=='-';
            c=getchar();
        }
        while(isdigit(c))
        {
            x=(x<<1)+(x<<3)+(c^48);
            c=getchar();
        }
        return w?-x:x;
    }
    template<typename ty>
    void out(ty x)
    {
        if(x<0)putchar('-'),x=-x;
        if(x>9)out(x/10);
        putchar(x%10+48);
    }
}
using usegetin::in;using usegetin::out;
using namespace std;
int l1,l2,prel[maxn],dc;//prel就是上文的prel
string s1,s2;
int main()
{
    cin>>s1>>s2;
    l1=s1.size();l2=s2.size();
    for(register int i=1;i<l2;i++)
    {
        while(dc&&s2[dc]^s2[i])dc=prel[dc-1];
        if(s2[dc]==s2[i])dc++;
        prel[i]=dc;
    }
    dc=0;
    for(register int i=0;i<l1;i++)
    {
        while(dc&&s2[dc]^s1[i])dc=prel[dc-1];
        if(s2[dc]==s1[i])dc++;
        if(dc==l2)
        {
            out(i-l2+2);pc('\n');
            dc=prel[dc-1];
        }
    }
    for(register int i=0;i<l2;i++)
    {
        out(prel[i]);pc(' ');
    }
    return 0;
}

扩展 KMP（Z Algorithm）

切记是只有在 $z_{i-l}$ 小于 $r-i+1$ 的时候直接赋值，不然不能保证原字符串 $s$（下标从0开始）中 $s_{i-l+1}\not =s_{r+1}$。

#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>//75760209
#include<ctime>
#include<climits>
#include<random>
#include<algorithm>
#include<unordered_set>
#define fru(i,j,k) for(register int i=j;i<=k;i++)//for_register_up
#define frd(i,j,k) for(register int i=j;i>=k;i--)//for_register_down
#define pc(charx) putchar(charx)
#define finfout(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using ll = long long;
namespace usegetin{
    char c=' ';
    inline ll in()
    {
        ll x=0;bool w=false;
        while(!isdigit(c))
        {
            w|=c=='-';
            c=getchar();
        }
        while(isdigit(c))
        {
            x=(x<<1)+(x<<3)+(c^48);
            c=getchar();
        }
        return w?-x:x;
    }
    template<typename ty>
    void out(ty x)
    {
        if(x<0)putchar('-'),x=-x;
        if(x>9)out(x/10);
        putchar(x%10+48);
    }
}
using usegetin::in;using usegetin::out;
using namespace std;
string s1,s2;
int nl[maxn],l2;//nl就是z数组
ll ans,ftl2,tmp,ans1;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);//这题好卡
    cin>>s1>>s2;
    register ll i,l,r;
    ftl2=s2.size();
    s2=s2+'$'+s1;
    l2=s2.size();
    for(i=1,l=0,r=0;i<l2;i++)
    {
        if(i<=r&&nl[i-l]<r-i+1)tmp=nl[i-l];
        else 
        {
            tmp=max(0ll,r-i+1);
            while(i+tmp<l2&&s2[tmp]==s2[i+tmp])++tmp;
        }
        if(r<i+tmp-1)l=i,r=i+tmp-1;
        if(i<ftl2)
        {
            ans1^=((i+1)*(tmp+1));
            nl[i]=tmp;
        }
        else if(i^ftl2)ans^=(i-ftl2)*(tmp+1);
    }
    out(ans1^(ftl2+1));pc('\n');
    out(ans);
    return 0;
}

AC 自动机

基本

简单版，可以通过P3808 【模板】AC 自动机（简单版）。

#include<bits/stdc++.h>
#define fru(i,j,k) for(int i=j;i<=k;i++)
#define frd(i,j,k) for(int i=j;i>=k;i--)
#define fio(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
using ll = long long;
char c=' ';
int in(void)
{
    int x=0;bool f=false;
    while(!isdigit(c)){f^=c=='-';c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}
const int maxn=1000012;
int n,tre[maxn][26],fail[maxn],tot,lin[maxn],ans;
char s[maxn];
void intre(char* s)
{
    int len=strlen(s),t=0;
    for(int i=0;i<len;i++)
    {
        if(!tre[t][s[i]-'a'])tre[t][s[i]-'a']=++tot;
        t=tre[t][s[i]-'a'];
    }
    lin[t]++;
}
void bd(void)
{
    queue<int>que;
    for(int i=0;i<26;i++)if(tre[0][i])que.emplace(tre[0][i]);
    int dc;
    while(!que.empty())
    {
        dc=que.front();que.pop();
        // cout<<dc<<' '<<fail[dc]<<endl;
        for(int i=0;i<26;i++)
        if(tre[dc][i])
        {
            fail[tre[dc][i]]=tre[fail[dc]][i];
            que.emplace(tre[dc][i]);
        }
        else tre[dc][i]=tre[fail[dc]][i];
    }
}
int main()
{
    n=in();
    fru(i,1,n)
    {
        scanf("%s",s);
        intre(s);
    }
    bd();scanf("%s",s);
    int len=strlen(s),dc=0;
    for(int i=0;i<len;i++)
    {
        dc=tre[dc][s[i]-'a'];
        for(int j=dc;j;j=fail[j])
        {
            if(lin[j]==-1)break;
            ans+=lin[j];lin[j]=0;
        }lin[dc]=-1;
    }
    printf("%d",ans);
    return 0;
}

多测

P3796 【模板】AC 自动机（加强版）告诉了我们多测要清零，否则会寄。

#include<bits/stdc++.h>
#define fru(i,j,k) for(int i=j;i<=k;i++)
#define frd(i,j,k) for(int i=j;i>=k;i--)
#define fio(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
using ll = long long;
char c=' ';
int in(void)
{
    int x=0;bool f=false;
    while(!isdigit(c)){f^=c=='-';c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}
const int maxn=1000012;
int n,tre[maxn][26],fail[maxn],tot,lin[maxn],cnt[maxn],ans,T,ts,sta[maxn];
char s[maxn],sl[maxn][80];
vector<int>vl[maxn];
int intre(char* s)
{
    int len=strlen(s),t=0;
    for(int i=0;i<len;i++)
    {
        if(!tre[t][s[i]-'a'])tre[t][s[i]-'a']=++tot;
        t=tre[t][s[i]-'a'];
    }
    lin[t]++;
    return t;
}
void bd(void)
{
    queue<int>que;
    for(int i=0;i<26;i++)if(tre[0][i])que.emplace(tre[0][i]);
    int dc;
    while(!que.empty())
    {
        dc=que.front();que.pop();
        // cout<<dc<<' '<<fail[dc]<<endl;
        for(int i=0;i<26;i++)
        if(tre[dc][i])
        {
            fail[tre[dc][i]]=tre[fail[dc]][i];
            que.emplace(tre[dc][i]);
        }
        else tre[dc][i]=tre[fail[dc]][i];
    }
}
int main()
{
    int len,dc;
    while(1)
    {
        fru(i,0,tot)
        {
            memset(tre[i],0,sizeof tre[i]);
            lin[i]=0;
            fail[i]=0;
            cnt[i]=0;
            vl[i].clear();
        }
        ts=ans=tot=0;

        n=in();
        if(!n)return 0;
        fru(i,1,n)
        {
            scanf("%s",sl[i]);
            vl[intre(sl[i])].emplace_back(i);
        }
        scanf("%s",s);
        bd();
        len=strlen(s);dc=0;
        for(int i=0;i<len;i++)
        {
            dc=tre[dc][s[i]-'a'];
            for(int j=dc;j;j=fail[j])
            if(lin[j])
            {
                ans=max(ans,++cnt[j]);
            }
        }
        printf("%d\n",ans);
        fru(i,1,tot)if(cnt[i]==ans)
        {
            for(auto j:vl[i])sta[++ts]=j;
        }
        sort(sta+1,sta+ts+1);
        fru(i,1,ts)
        {
            printf("%s\n",sl[sta[i]]);
        }
        // fru(i,1,ts)cout<<sta[i]<<endl;
    }
    return 0;
}

优化

考虑到在 fail 指针构成的图中，每个点出度为一且没有环，因此该图是树，于是可以拓扑序优化，通过P5357 【模板】AC 自动机（二次加强版）。

#include<bits/stdc++.h>
#define fru(i,j,k) for(int i=j;i<=k;i++)
#define frd(i,j,k) for(int i=j;i>=k;i--)
#define fio(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
using ll = long long;
// char c=' ';
// int in(void)
// {
//     int x=0;bool f=false;
//     while(!isdigit(c)){f^=c=='-';c=getchar();}
//     while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
//     return f?-x:x;
// }
const int maxn=2000012;
int n,tre[maxn][26],in[maxn],fail[maxn],at[maxn],ans[maxn],tot;//tot for trie
string sl[maxn],s;
vector<int>vl[maxn];
int intre(string &s)
{
    int t=0,len=s.size();
    for(int i=0;i<len;i++)
    {
        if(!tre[t][s[i]-'a'])tre[t][s[i]-'a']=++tot;
        t=tre[t][s[i]-'a'];
        // cout<<t<<' ';
    }
    // cout<<endl;
    return t;
}
queue<int>que;
void bd(void)
{
    for(int i=0;i<26;i++)if(tre[0][i])que.emplace(tre[0][i]);
    int dc;
    while(!que.empty())
    {
        dc=que.front();que.pop();
        for(int i=0;i<26;i++)
        {
            if(tre[dc][i])
            {
                fail[tre[dc][i]]=tre[fail[dc]][i];
                // cout<<tre[dc][i]<<' '<<fail[tre[dc][i]]<<endl;
                in[fail[tre[dc][i]]]++;
                que.emplace(tre[dc][i]);
            }else tre[dc][i]=tre[fail[dc]][i];
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    fru(i,1,n)
    {
        cin>>sl[i];
        vl[intre(sl[i])].emplace_back(i);
    }
    bd();
    cin>>s;
    int dc=0,len=s.size();
    for(int j=0;j<len;j++)
    {
        dc=tre[dc][s[j]-'a'];
        at[dc]++;
    }
    // fru(i,1,tot)
    // {
    // 	cout<<"in:"<<in[i]<<endl;
    // }
    fru(i,1,tot)if(!in[i])que.emplace(i);
    while(!que.empty())
    {
        dc=que.front();que.pop();
        // cout<<"dc:"<<dc<<endl;
        at[fail[dc]]+=at[dc];
        if(!(--in[fail[dc]]))que.emplace(fail[dc]);
    }
    fru(i,1,tot)for(auto j:vl[i])ans[j]=at[i];
    fru(i,1,n)
    {
        cout<<ans[i]<<endl;
    }
    return 0;
}

manacher 算法

马拉车

思路比较简单，所以还是直接放板子题代码：

#include<bits/stdc++.h>
#define fru(i,j,k) for(register ll i=j;i<=k;i++)
#define frd(i,j,k) for(register ll i=j;i>=k;i--)
#define fio(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
using ll = long long;
char c=' ';
ll in(void)
{
    ll x=0;bool f=false;
    while(!isdigit(c)){f^=c=='-';c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x ;
}
const int maxn=30000012;
int n,dc,ml[maxn],ans,tot;
char s[maxn],s1[maxn];
int main()
{
    scanf("%s",s);
    n=strlen(s);
    s1[tot]='@';
    for(int i=0;i<n;i++)
    {
        s1[++tot]=s[i];
        s1[++tot]='@';
    }
    n=n<<1|1;
    for(int l=0,r=-1,i=0;i<n;i++)
    {
        dc=(i>r)?1:min(ml[l+r-i],r-i)+1;
        while(i>=dc&&s1[i-dc]==s1[i+dc])dc++;
        ml[i]=--dc;
        if(i+dc>r)
        {
            r=i+dc;
            l=i-dc;
        }
        ans=max(ans,ml[i]);
    }
    printf("%d",ans);
    return 0;
}

后缀系列

后缀数组（SA）

注意看注释！

模板题链接

#include<bits/stdc++.h>
#define fru(i,j,k) for(int i=j;i<=k;i++)
#define frd(i,j,k) for(int i=j;i>=k;i--)
#define pc(x) putchar(x)
#define fio(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
using namespace std;using ll = long long;
namespace ugi{
char c=' ';
int in(void)
{
    int x=0;bool f=false;
    while(!isdigit(c)){f^=c=='-';c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}
}
using ugi::in;
const int maxn=1000012;
int n,sa[maxn],rk[maxn],cnt[maxn],p,w,m,id[maxn],ok[maxn<<1],tk[maxn];//ok:old_rank m为上一步rk的值域，m到达n则rk无冲突
string s;
inline bool cmp(int x,int y)
{
    return ok[x]==ok[y]&&ok[x+w]==ok[y+w];
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>s;n=s.size();m=127;
    fru(i,1,n)++cnt[rk[i]=s[i-1]];
    fru(i,1,m)cnt[i]+=cnt[i-1];
    frd(i,n,1)sa[cnt[rk[i]]--]=i;
    for(w=1;w<=n;w<<=1,m=p)
    {
        p=0;for(int i=n;i>n-w;--i)id[++p]=i;
        fru(i,1,n)if(sa[i]>w)id[++p]=sa[i]-w;//sa枚举第一关键字 id枚举第二关键字 rk枚举字符串下标
        memset(cnt,0,m*sizeof(int));
        fru(i,1,n)++cnt[tk[i]=rk[id[i]]];//对id[i]排序而不是对i排序
        fru(i,1,m)cnt[i]+=cnt[i-1];
        frd(i,n,1)sa[cnt[tk[i]]--]=id[i];//此时sa已经为最终结果
        memcpy(ok+1,rk+1,n*sizeof(int));
        p=0;fru(i,1,n)rk[sa[i]]=cmp(sa[i],sa[i-1])?p:++p;
        if(p==n)break;
    }
    fru(i,1,n)
    {
        cout<<sa[i]<<" ";
    }
    return 0;
}