Suffix Automaton

int last,num;
struct node{
    
    int fa,len,sum;
    int son[26];
}t[maxn*2];



void extend(int c){
          // Each direction SAM Insert an element in c
    p=last,np=++num;
    t[np].len=t[p].len+1;np=num;cc[np]=1;
    while(p&&!t[p].son[c])t[p].son[c]=np,p=t[p].fa;
    if(!p)t[np].fa=1;
    else{
    
        q=t[p].son[c];
        if(t[p].len+1==t[q].len)t[np].fa=q;
        else{
    
            nq=++num;
            t[nq]=t[q];
            t[num].len=t[p].len+1;
            t[q].fa=t[np].fa=nq;
            while(p&&t[p].son[c]==q)t[p].son[c]=nq,p=t[p].fa;
        }
    }
    last=np;
}


fo(i,1,n)extend(s[i]-'a');

application

1、 The longest common substring of two strings

Build out A Suffix automata of strings , then B String runs on suffix automata .

 link ：https://www.nowcoder.com/questionTerminal/181a1a71c7574266ad07f9739f791506
 source ： Cattle from 

#include<iostream>
#include<string>
using namespace std;
int main()
{
    
    string a, b;
    while (cin >> a >> b)
    {
    
        if (a.size() > b.size())
            swap(a, b);
        string str_m;// Store the longest common substring 
        for (int i = 0; i < a.size(); i++)
        {
    
            for (int j = i; j < a.size(); j++)
            {
    
                string temp = a.substr(i, j - i + 1);
                    if (int(b.find(temp))<0)
                    break;
                else if (str_m.size() < temp.size())
                    str_m = temp;
            }
        }
        cout << str_m << endl;
    }
    return 0;+

2、 Find the number of different substrings

Method 1 ： use dfs How many strings can be extended at each point of processing s u m [ x ] = ∑ s u m [ t [ x ] . s o n [ i ] ] + 1 sum[x]=\sum sum[t[x].son[i]]+1sum[x]=∑sum[t[x].son[i]]+1, You don't have to dfs, Topology （ Press len From small to large ） Then do it backwards . Last sum[1] Is the number of all substrings .
Method 2 ：a n s = ∑ t [ x ] . l e n − t [ t [ x ] . f a ] . l e n ans=\sum t[x].len-t[t[x].fa].lenans=∑t[x].len−t[t[x].fa].len, Here we use properties 1, Because of the node i The string size range represented is from len[fa[i]]+1…len[i] Of , Then the number of different strings =l e n [ i ] − ( l e n [ f a [ i ] ] + 1 ) + 1 = l e n [ i ] − l e n [ f a [ i ] ] len[i]-(len[fa[i]]+1)+1=len[i]-len[fa[i]]len[i]−(len[fa[i]]+1)+1=len[i]−len[fa[i]]

3、 Find the first K Big string

1、 Find the number of different strings K Big ： Preprocess how many strings each state can construct , It can be used dfs do , You can also talk about the topology of automata （ In fact, it is equivalent to len Sort from small to large , because len A small topological order is also small ）, Then ask backwards （ amount to DAG Upper DP）, then dfs Look for number one K A big one would be fine .
2、 Find the first of the same string K Big ： In addition to preprocessing the above things , Also preprocess out all States right The size of the collection （ How many times each string appears in the original string ）, This will affect the value of the above requirements , And then doing dfs It's good to deal with it at the same time .
The original title is TJOI2015 String theory

4、 Find the minimum cyclic representation

The minimum cyclic representation is the string with the smallest lexicographic order among all cyclic strings of this string .
Copy the original string to the back , Then establish suffix automata , The point with the smallest dictionary order each time , Walk until the length is |S| until .

5、 Find the string

Construct the suffix automaton of the original string , Find out every node right A collection of rmax, Then put the inverse string on the suffix automata to run , If the current matching string is within the range of the original string [l…r] Overwrites the current node rmax, that [l…rmax] It's a palindrome string .

6、Trie Shangjian SAM

It looks very advanced , In fact, it's each node's last Namely trie Parent node on . Why are you in trie Shangjian ？
For example, it is necessary to establish suffix automata for many strings at the same time , So there are two ways ：
Method 1 ： Separate all strings with a different character , Then establish suffix automata .
Method 2 ： Put all the strings into one trie On , And then in trie Build suffix automata on .（ In fact, this seems to be also called generalized suffix automata ）