字符串算法汇总

字符串哈希：

讲解

大意就是将字符串视为一个多位的数，用unsigned long long 保存，溢出可以视为对2^64取模。

回文树： 

博客

另一篇博客

推荐配合OIWiki上的图食用

每个节点代表当前前缀的最大回文串后缀，next指向的是代表[通过前后加上一个新字符能得到的新回文串]的节点，suffix指向的是加入新字符后，该回文串的最大的回文后缀。有两个根，最终节点数-2就是回文串总数。

后缀自动机：

讲解和应用直接推荐OIwiki了，传送门

这篇作为补充https://oi.men.ci/suffix-automaton-notes/

后缀自动机记录某个字符串所有的子串信息。每个节点都代表了一类子串，这些子串有相同的endpos集合。节点的next指向在添加新字符后形成的新子串集合。link（fail）指向拥有更大endpos集合的最长后缀（这也是为什么算法叫后缀自动机，后缀链接是本算法的核心）即link[p]是第一个拥有更多出现次数的p的后缀。maxlen(link[p])=minlen(p)-1。

所谓广义后缀自动机，即同时包含有多个字符串的后缀自动机，构造方法很多。效率最好的一种通过建立字典树bfs，目前还未掌握，留待填坑。也可以选择每处理完一个字符串，将last置零，再添加下一个字符串

回文树+广义后缀自动机：

牛客2019多校I：链接

代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+2;
struct state{
    int len,link;
    map<char,int>next;    //如果是需要多次使用的自动机，可将next改为数组实现，方便清零
};
state st[maxn*4];
int sz,last;
void sam_init(){
    st[0].len=0;
    st[0].link=-1;
    sz=1;
    last=0;
}
void sam_extend(char c){
    int cur=sz++;
    st[cur].len=st[last].len+1;
    int p=last;
    while(p!=-1&&!st[p].next.count(c)){
        st[p].next[c]=cur;
        p=st[p].link;
    }
    if(p==-1){
        st[cur].link=0;
    }else{
        int q=st[p].next[c];
        if(st[p].len+1==st[q].len){
            st[cur].link=q;
        }else{                //考虑到q可能由其他拥有不同前缀的子串延申而来（更长）
            int clone=sz++;
            st[clone].len=st[p].len+1;
            st[clone].next=st[q].next;
            st[clone].link=st[q].link;
            while(p!=-1&&st[p].next[c]==q){
                st[p].next[c]=clone;
                p=st[p].link;
            }
            st[q].link=st[cur].link=clone;
        }
    }
    last=cur;
}

long long count_sub(){
    long long res=0;
    for(int i=1;i<=sz;i++){
        res+=st[i].len-st[st[i].link].len;
    }
    return res;
}

struct palindrome_tree{
    map<char,int> trans[maxn];
    int len[maxn],suf[maxn],num[maxn];
    int lst,cnt;
    char s[maxn];

    palindrome_tree(char* _s){
        memcpy(s,_s,strlen(_s));
    }
    int new_node(int _len,int _suf,int _num){
        len[cnt]=_len;
        suf[cnt]=_suf;
        num[cnt]=_num;
        return cnt++;
    }

    void init(){
        cnt=0;
        new_node(0,1,0);
        int odd_root=new_node(-1,1,0);
        lst=odd_root;
    }

    void extend(int cur){
        char c=s[cur];
        int p=lst;
        while(s[cur-len[p]-1]!=s[cur])
            p=suf[p];
        if(!trans[p].count(c)){
            int v=suf[p];
            while(s[cur-len[v]-1]!=s[cur])    //给新串找后缀suf
                v=suf[v];
            trans[p][c]=new_node(len[p]+2,trans[v][c],0);
        }
        lst=trans[p][c];
        num[lst]++;
    }

    int count_pa(){
        return cnt-2;
    }


};

int main(){
    char s[maxn];
    while(~scanf("%s",s)){
        int len=strlen(s);
        sam_init();
        for(int i=0;i<len;i++)
            sam_extend(s[i]);
        last=0;
        for(int i=len-1;i>=0;i--)
            sam_extend(s[i]);

        palindrome_tree* pa=new palindrome_tree(s);
        pa->init();
        for(int i=0;i<len;i++)
            pa->extend(i);
//        int tst=count_sub();
        long long ans=(count_sub()+pa->count_pa())/2;
        cout<<ans<<endl;
    }
}

 

后缀数组：

讲解链接，虽然网上大多用的是另一套板子，不过OIwiki上的这版变量名更清楚一些。

需要用到基数排序的知识，不熟悉的建议先去巩固这方面的知识。整个算法过程分为建立后缀数组SA，获取高度（名次相邻的两个后缀的最长前缀），以及为了方便求任意两个后缀的lcp的ST表的初始化工作。

例题：传送门

#include<bits/stdc++.h>

using namespace std;

const int N=300000+10;
char s[N],buf[N];
int n,k,len1,t;
vector<int> v1,v2;
int sa[N],rnk[N],cnt[N],height[N],ST[N][20];
void getSA(int m=300){
    static int cnt[N],rnk1[N],rnk2[N],tmpSA[N];
    fill(cnt,cnt+m,0);
    for(int i=0;i<n;i++) cnt[(int)s[i]]++;
    for(int i=1;i<m;i++) cnt[i]+=cnt[i-1];
    for(int i=0;i<n;i++) rnk[i]=cnt[(int)s[i]]-1;
    for(int l=1;l<n;l<<=1){
        for(int i=0;i<n;i++){
            rnk1[i]=rnk[i];
            rnk2[i]=(i+l<n?rnk1[i+l]:0);
        }
        fill(cnt,cnt+m,0);
        for(int i=0;i<n;i++) cnt[rnk2[i]]++;
        for(int i=1;i<m;i++) cnt[i]+=cnt[i-1];
        for(int i=n-1;i>=0;--i) tmpSA[--cnt[rnk2[i]]]=i;
        fill(cnt,cnt+m,0);
        for(int i=0;i<n;i++) cnt[rnk1[i]]++;
        for(int i=1;i<m;i++) cnt[i]+=cnt[i-1];
        for(int i=n-1;i>=0;i--) sa[--cnt[rnk1[tmpSA[i]]]]=tmpSA[i];
        bool uniq=true;
        rnk[sa[0]]=0;    //判断是否已排好，同时求一下rnk的值
        for(int i=1;i<n;i++){
            rnk[sa[i]]=rnk[sa[i-1]];
            if(rnk1[sa[i]]==rnk1[sa[i-1]]&&rnk2[sa[i]]==rnk2[sa[i-1]])
                uniq=false;
            else
                rnk[sa[i]]++;
        }
        if(uniq)
            break;
    }
}

void getheight(){
    int k=0;
    for(int i=0;i<n;i++){
        if(!rnk[i])
            continue;
        if(k)
            --k;
        int j=sa[rnk[i]-1];
        while(s[i+k]==s[j+k])
            ++k;
        height[rnk[i]]=k;
    }
}

void initST(){
    for(int i=0;i<n;i++)
        ST[i][0]=height[i];
    for(int j=1;(1<<j)<=n;j++){
        for(int i=0;i+(1<<j)-1<n;i++)
            ST[i][j]=min(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
    }
}

以上为基础的三步。后缀数组中有一个经常用的结论，就是某个后缀和其他后缀的lcp，一定是和字典序相邻的两个后缀产生的。其次在求height时，运用了结论height[rnk[i]]>height[rnk[i-1]]-1

void build(){
    getSA();
    getheight();
    initST();
}

int lcp(int l,int r){
    if(l==r)
        return n-sa[l];
    if(l>r)
        swap(l,r);
    l++;
    int k=0;
    while(1<<(k+1)<=r-l+1) ++k;
    return min(ST[l][k],ST[r-(1<<k)+1][k]);
}

void solve(){
    v1.clear();
    v2.clear();
    for(int i=0;i<n;i++){
        if(sa[i]<len1)
            v1.push_back(sa[i]);
        else
            v2.push_back(sa[i]);
    }
    int ansp,anslen=0x3f3f3f3f;
    for(int i=0,j=0;i<v1.size();i++){
        while(j<v2.size()&&rnk[v2[j]]<rnk[v1[i]])
            j++;
        int maxlen=-1;
        if(j>0)
            maxlen=max(maxlen,lcp(rnk[v2[j-1]],rnk[v1[i]]));
        if(j<n)
            maxlen=max(maxlen,lcp(rnk[v2[j]],rnk[v1[i]]));
        if(maxlen<anslen&&v1[i]+maxlen<len1){
            anslen=maxlen;
            ansp=v1[i];
        }
    }
    if(anslen!=0x3f3f3f3f){
        for(int i=ansp;i<=ansp+anslen;i++)
            printf("%c",s[i]);
    }else{
        printf("Impossible");
    }
    puts("");
}

int main(){
    scanf("%d",&t);
    n=0;
    for(int i=0;i<t;i++){
        scanf("%s",buf);
        int len=strlen(buf);
        if(i==0)
            len1=len;
        else
            s[n++]='z'+1;
        for(int i=0;i<len;++i)
            s[n++]=buf[i];
    }
    s[n]='\0';
    build();
    solve();
    return 0;
}