7.28SAM后缀自动机，回文自动机

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 20 ; 
struct SAM{int t[N][26] , link[N] , len[N];int last ,tot ; SAM() : last(1) , tot(1){}void insert(int c){int p = last , np = last = ++tot ; //p是之前的节点 np是现新建的节点len[np] = len[p] + 1 ; //首先会多一个endpos为n的，其他的不可能和他重复while( p and !t[p][c] )t[p][c] = np , p = link[p];//link[p]相当于fail指针 向上跳使得s -> s的后缀 在后缀上->一个 就相当于是一个新的子串if(!p)link[np] = 1 ;//如果跳到根了，说明没有与他相同的子串，所以失配只能跳到根else{//如果有和他一样的子串int q = t[p][c] ; if( len[q] == len[p] + 1)link[np] = q ;//如果说是s+c的等价后继类是s的等价类最长的+1 ,那么他就是等价后继类else{int nq = ++tot ; memcpy( t[nq] , t[q] , sizeof(t[q]));//转移函数不变len[nq] = len[p] + 1 ; //新加了一个c所以长度+1link[nq] = link[q] ;///*如图nq/  \q    np */link[np] = link[q] = nq ;//while( p and t[p][c] == q )t[p][c] = nq , p = link[p];//更新其他的到他的节点}}}
}