对于一个关于只接受strstr后缀的后缀自动机,其后缀肯定能从起始状态SS合理地转移,而非后缀必然无法转移

定义

定义相关的函数

trans[u][ch]=vtrans[u][ch]=v:表示uu状态沿着chch边转移到了vv状态的转移函数

endpos(s)endpos(s):表示strstr的任意子串ss的终止位置集合,用于子串归类

性质1:当len(s1)len(s2)len(s1) \le len(s2)endpos(s1)endpos(s1)包含endpos(s2)endpos(s2)所有子集时,s2s2s1s1的后缀(充要)

当两个集合endpos(s1)==endpos(s2)endpos(s1)==endpos(s2),则认为子串s1s1s2s2属于同一类

对于每一个相同的归类都设为一个状态,假定其中一个为uu

substr(u)substr(u):表示归为同一状态uu的所有子串集合

longest(u)longest(u)substr(u)substr(u)中最长的子串

shortest(u)shortest(u)substr(u)substr(u)中最短的子串

性质2:substr(u)substr(u)中每一个子串ss都是longest(u)longest(u)的后缀;longest(u)longest(u)的后缀中满足len(s)len(shortest(u))len(s) \le len(shortest(u))的都属于状态uu,既substr(u)substr(u)

有了前面的东西就可以考虑一定的优化如下

slink[u]=vslink[u]=v:我们用suffix link来表示不属于该状态的longest(u)longest(u)的后缀(由性质1,由于长度小而无法表示不包含的endposendpos则用slinkslink连接起来,直到起始状态SS为止;slink[u]=vslink[u]=v的沿向一定是endpos(v)endpos(v)逐渐包含endpos(u)endpos(u)的过程,而endpos(S)endpos(S)则包含所有位置)

minlen[u],maxlen[u]minlen[u],maxlen[u]:分别表示状态uu中最短和最长的字符串的长度(由性质2,这些都是连续的后缀,无需多余记录真实的字符串)

为此我们用slinkslink替代了endposendpos,同时minlen,maxlenminlen,maxlen替代了substr,shortest,longestsubstr,shortest,longest

构造过程

  • 考虑增量法,假设已经构造好str[1...i]str[1...i]的后缀自动机,如何在线增加一个str[i+1]str[i+1](设为chch)以满足str[j...i+1],1ji+1str[j...i+1],1 \le j \le i+1的构造
  • 至少str[1...i+1]str[1...i+1]肯定没有重复的出现在原有的任一状态中,假设新增的状态为uu,令str[1...i]str[1...i]所在的状态vv(此前最后一个新增的状态)新增转移trans[v][ch]=utrans[v][ch]=u(此时也表示了str[j...i],1jnminlen(u)+1str[j...i],1 \le j \le n-minlen(u)+1的转移),并沿着slink[v]=wslink[v]=w的路径,对所有的trans[w][ch]=nulltrans[w][ch]=null都把对应转移指向uu
  • 对于第一个已经存在先前的状态xx满足trans[w][ch]=xtrans[w][ch]=x的情况,需要分两类考虑
  • 一类是maxlen[w]+1=maxlen[x]maxlen[w]+1=maxlen[x],此时表明该状态xx完全重复且无多余地覆盖了str[j...i+1]str[j...i+1]的后缀,那么只需slink[u]=xslink[u]=x,结束流程
  • 另一类是maxlen[w]+1<maxlen[x]maxlen[w]+1 \lt maxlen[x],此时需要划分原有的xx的子串为三个部分,minlen[x]...maxlen[w]+1...maxlen[x]minlen[x]...maxlen[w]+1...maxlen[x],考虑把状态xx拆分出一部分yy来继承原有[minlen[w],maxlen[w]+1][minlen[w],maxlen[w]+1]的部分,xx只包含剩下的部分(此时slink[y]=slink[x],slink[x]=yslink[y]=slink[x],slink[x]=y),那么状态yy的出现使得问题回归到上一类的情况,只需trans[w][ch]=y,slink[u]=ytrans[w][ch]=y,slink[u]=y
  • 对于上面的转移可能不止一个ww转移向原xx,所以需要把连续的trans[w][ch]trans[w][ch]置为yy

完成版

#include<bits/stdc++.h>
#define fast_io() do{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);}while(0)
using namespace std;

namespace util {
    template<typename T>
    inline void alloc(vector<T> &v) {
        v.emplace_back();
    }
    template<typename T>
    inline void empb(vector<T> &v,T &arg) {
        v.emplace_back(arg);
    }
}

using namespace util;
struct SuffixAutomaton {
    vector<array<int,26>> trans;
    vector<int> slink,minlen,maxlen;
    int last;
    
    inline void init() {
        alloc(trans);
        alloc(slink);
        alloc(minlen);
        alloc(maxlen);
    }
    
    SuffixAutomaton() {
        init();
        last = 0;
        slink[0] = -1;
        minlen[0] = maxlen[0] = 0;
        trans[0].fill(-1);
    } 
    
    int state(int tr,int suf,int mn,int mx) {
        int cur = trans.size();
        alloc(trans);
        if(~tr) trans[cur] = trans[tr];
        else trans[cur].fill(-1);
        empb(slink,suf);
        empb(minlen,mn);
        empb(maxlen,mx);
        return cur;
    }
    
    int add(char ch) {
        int c = ch - 'a';
        int u = state(-1,-1,-1,maxlen[last]+1);
        int v = last;
        while(v!=-1 && trans[v][c] == -1) {
            trans[v][c] = u;
            v = slink[v];
        }
        if(v == -1) {
            minlen[u] = 1;
            slink[u] = 0;
            return last = u;
        }
        int x = trans[v][c];
        if(maxlen[v]+1 == maxlen[x]) {
            slink[u] = x;
            minlen[u] = maxlen[x]+1;
            return last = u;
        }
        int y = state(x,-1,-1,maxlen[v]+1);
        minlen[y] = maxlen[slink[y] = slink[x]]+1;
        minlen[x] = maxlen[slink[x] = y]+1;
        minlen[u] = maxlen[slink[u] = y]+1;
        while(v != -1 && trans[v][c] == x) {
            trans[v][c] = y;
            v = slink[v];
        }
        return last = u;
    }
};

int main() {
    fast_io();
    string str;
    cin >> str;
    SuffixAutomaton sam;
    for(int i = 0; str[i]; i++) {
        sam.add(str[i]);
    }
    long long res = 0;
    for(int i = 1; i < sam.trans.size(); i++) {
        res += sam.maxlen[i]-sam.minlen[i]+1;
    } 
    cout << res << endl;
    return 0;
}

old version: https://paste.ubuntu.com/p/TjFs5wVS8d/

参考

hihocoder127/128解题方法提示