一、后缀自动机基本概念的理解

1、首先后缀自动机的状态是由子串的endpos来决定的

子串的endpos是指一个子串可以在原字符串的哪些位置进行匹配，

endpos构成的不同集合划分成不同的状态

关于endpos的性质： s1是s2的子串当且仅当endpos(s1)属于endpos(s2)，s1不是s2的子串当前仅当endpos(s1)和endpos(s2)的交集为空

2、对于一个用endpos划分的状态，最长的子串为longest(st)，最短的为shortest(st)，对于任何包含于该状态的子串，都是longest(st)的后缀；同样，对于一个状态中的longest(st)的后缀，如果后缀的长度在longest和shortest之间，那么它就属于这个状态。

如此可以这样理解，一个endpos划分的状态，实际上是longest形成的一系列后缀

3、Link

link是将不同endpos间连接起来的边，实际上是把系列的中断相连

4、Transition function

对于一个状态，首先找到它下一个可能出现的字符有哪些，实际上就是只需要把longest后面添加一下新的字符，然后看这个新的串被哪个状态所包含

那么它的那一系列后缀也被这个状态所包含。

 

暴力做法 （关于endpos）

hihocoder 1441

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define fi first#define se secondusing namespace std;typedef pair
         
           PII;char str[100], temp[100];vector
          
            endpos[100][100];int n;bool ok(int x, int y, int t){ int len = y-x+1; int s = t-len+1; if(s < 0) return false; for(int i = 0; i < len; i++) if(str[i+x] != str[s+i]) return false; return true;}bool cmp(int x, int y, char* temp){ int len = y-x+1; if(len != strlen(temp)) return false; for(int i = 0; i < len; i++) if(str[i+x] != temp[i]) return false; return true;}void print(char* str, int x, int y){ for(int i = x; i <= y; i++) cout<
           
            >str; int len = strlen(str); for(int i = 0; i < len; i++){ for(int j = i; j < len; j++) for(int k = 0; k < len; k++) if(ok(i, j, k)) endpos[i][j].push_back(k+1); } cin>>n; while(n--){ cin>>temp; PII s; for(int i = 0; i < len; i++) for(int j = i; j < len; j++) if(cmp(i, j, temp)) { s = {i, j}; break; } auto x = endpos[s.fi][s.se]; int longest = 0, shortest = 1e9; PII ll, ss; for(int i = 0; i < len; i++) for(int j = i; j < len; j++){ auto y = endpos[i][j]; if(x.size() != y.size()) continue; int fail = 0; for(int k = 0; k < x.size(); k++) if(x[k] != y[k]) fail = 1; if(fail) continue; if(longest < j-i+1) { longest = j-i+1; ll = {i, j}; } if(shortest > j-i+1) { shortest = j-i+1; ss = {i, j}; } } print(str, ss.fi, ss.se); cout<<" "; print(str, ll.fi, ll.se); cout<<" "; for(auto tt : x) cout<
            <<" "; cout<
           
          
         
        
       
      
     

 

 

二、算法部分

hihocoder上讲的很详细

但是只是给出了实现的做法，算法的正确性并没有给出详尽的证明，以后看情况补充吧（挖坑）

算法分成三种情况。运用增量法，取上一次的状态

顺着它的link走，可以得到它的所有后缀，所以就是所有后缀加上这次新的字符

首先建立一个新的状态z代表S[1...i+1]，maxlen显然是i+1

①如果link-path上都没有这个新的字符，就全部直接连新的状态，link[z] = s，更新minlen

②如果link-path上有一个状态x，它加上新的字符可以转移到另一个状态y，做如下处理

1、如果maxlen[x]+1 = maxlen[y]，那么说明实际上x是z的longest的一系列后缀，只不过不在同一状态中，所以直接link[z] = x即可，更新minlen

2、如果maxlen[x]+1 < maxlen[y]，那么我们就把y结点分成两部分，一部分p是maxlen[y] <= maxlen[x]+1，这部分实际上和1是一样的。另一部分q是maxlen[y] > maxlen[x] + 1

实际上x并不能转移到q，所以q留在原地，新建一个结点代表p，让x连向p，然后link[p] = x,  link[q] = link[z] = p。

对于剩下的link-path上的状态，如果它们连向y的话，就重新连向p。最后更新一下p的minlen

 

 

三、题目练习

hihocoder 1445

题目大意：给出一个串，求出不重复子串的个数

 

答案就是每个状态的longest减去shortest，可以保证没有重复的情况出现

 

#include 
     
      #include 
      
       #include 
       
        using namespace std;int n = 0, len, st;const int maxL = 1e6 + 100;int maxlen[2*maxL], minlen[2*maxL], trans[2*maxL][27], slink[2*maxL];int new_state(int _maxlen, int _minlen, int *_trans, int _slink){    maxlen[n] = _maxlen;    minlen[n] = _minlen;    for(int i = 0; i < 26; i++){        if(_trans == NULL)            trans[n][i] = -1;        else            trans[n][i] = _trans[i];    }    slink[n] = _slink;    return n++;}int add_char(char ch, int u){    int c = ch - 'a';    int z = new_state(maxlen[u]+1, -1, NULL, -1);    int v = u;    while(v != -1 && trans[v][c] == -1){        trans[v][c] = z;        v = slink[v];    }    if(v == -1){        minlen[z] = 1;        slink[z] = 0;        return z;    }    int x = trans[v][c];    if(maxlen[v] + 1 == maxlen[x]){        minlen[z] = maxlen[x] + 1;        slink[z] = x;        return z;    }    int y = new_state(maxlen[v] + 1, -1, trans[x], slink[x]);    slink[y] = slink[x];    minlen[x] = maxlen[y] + 1;    slink[x] = y;    minlen[z] = maxlen[y] + 1;    slink[z] = y;    int w = v;    while(w != -1 && trans[w][c] == x){        trans[w][c] = y;        w = slink[w];    }    minlen[y] = maxlen[slink[y]] + 1;    return z;}char str[maxL];int main(){    cin>>str;    st = new_state(0, 0, NULL, -1);    int len = strlen(str);    for(int i = 0; i < len; i++) {        st = add_char(str[i], st);    }    long long ans = 0;    for(int i = 1; i < n; i++) ans += (maxlen[i] - minlen[i] + 1);    cout<
        
         <
        
       
      
     

 

hihocoder 1449

给定一个串，要求求出长度为k的子串中重复最多的串出现的次数

 

问题实际上转换成了求endpos的大小

在建立完后缀自动机后，我们用link可以连接成一棵树

对于父结点的孩子若干个孩子，实际上我们有

endpos[fa] >= sigma(endpos[son])

一般情况下是等于的，但是如果这一点的状态恰好表示了一个前缀，那么就要加1

而前缀的那些点其实是加入的那些，所以加入的过程中标记一下即可

 

最后求答案的时候，对于一个状态我们实际上要用endpos[x]更新minlen[x] ~ maxlen[x]

但是实际上我们只需要更新maxlen，原因是答案一定是随长度递增的

所以最后做一个这样的处理 ans[i] = max(ans[i], ans[i+1]就可以了

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int n = 0, len, st;const int maxL = 1e6 + 100;int maxlen[2*maxL], minlen[2*maxL], trans[2*maxL][27], slink[2*maxL], lab[2*maxL], ans[2*maxL], son[2*maxL], endpos[2*maxL];int new_state(int _maxlen, int _minlen, int *_trans, int _slink){    maxlen[n] = _maxlen;    minlen[n] = _minlen;    for(int i = 0; i < 26; i++){        if(_trans == NULL)            trans[n][i] = -1;        else            trans[n][i] = _trans[i];    }    slink[n] = _slink;    return n++;}int add_char(char ch, int u){    int c = ch - 'a';    int z = new_state(maxlen[u]+1, -1, NULL, -1); lab[z] = 1;    int v = u;    while(v != -1 && trans[v][c] == -1){        trans[v][c] = z;        v = slink[v];    }    if(v == -1){        minlen[z] = 1;        slink[z] = 0;        return z;    }    int x = trans[v][c];    if(maxlen[v] + 1 == maxlen[x]){        minlen[z] = maxlen[x] + 1;        slink[z] = x;        return z;    }    int y = new_state(maxlen[v] + 1, -1, trans[x], slink[x]);    slink[y] = slink[x];    minlen[x] = maxlen[y] + 1;    slink[x] = y;    minlen[z] = maxlen[y] + 1;    slink[z] = y;    int w = v;    while(w != -1 && trans[w][c] == x){        trans[w][c] = y;        w = slink[w];    }    minlen[y] = maxlen[slink[y]] + 1;    return z;}char str[maxL];int main(){    cin>>str;    st = new_state(0, 0, NULL, -1);    int len = strlen(str);    for(int i = 0; i < len; i++) {        st = add_char(str[i], st);    }    for(int i = 1; i <= n; i++) son[slink[i]]++;    queue
         
           Q;    for(int i = 1; i <= n; i++) if(son[i] == 0) Q.push(i), endpos[i] = 1;    while(!Q.empty()){        int x = Q.front(); Q.pop();        if(x == 0) continue;        int y = slink[x];        son[y]--; endpos[y] += endpos[x];        if(son[y] == 0){            if(lab[y]) endpos[y]++;            Q.push(y);        }    }    for(int i = 1; i <= n; i++) ans[maxlen[i]] = max(ans[maxlen[i]], endpos[i]);    for(int i = len-1; i >= 1; i--) ans[i] = max(ans[i], ans[i+1]);    for(int i = 1; i <= len; i++) cout<
          
           <