rt，如果省选没退役就补
SAM的优势：简单明了
先建S的SAM并标记所有节点，之后每次询问直接把T按广义SAM的方法插上去，统计新加的节点到根的状态代表的本质不同子串数，减掉被标记的部分就是T独有的
1 #include<cstdio> 2 #include<vector> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=3000005; 7 int trs[N][26],fth[N],len[N],vis[N],ori[N]; 8 int T,t1,t2,lth,tot,lst,cnt,tmp,tep; 9 char str[N]; vector<int> vec; 10 int Insert(int ch) 11 { 12 int nde=lst,newn=++tot; 13 lst=newn,len[newn]=len[nde]+1; 14 while(nde&&!trs[nde][ch]) 15 trs[nde][ch]=newn,nde=fth[nde]; 16 if(!nde) fth[newn]=1; 17 else 18 { 19 int tran=trs[nde][ch]; 20 if(len[tran]==len[nde]+1) 21 fth[newn]=tran; 22 else 23 { 24 int rnde=++tot; 25 len[rnde]=len[nde]+1,ori[rnde]=ori[tran]; 26 for(int i=0;i<=25;i++) trs[rnde][i]=trs[tran][i]; 27 fth[rnde]=fth[tran],fth[tran]=fth[newn]=rnde; 28 while(nde&&trs[nde][ch]==tran) 29 trs[nde][ch]=rnde,nde=fth[nde]; 30 } 31 } 32 return newn; 33 } 34 void Clean() 35 { 36 for(int i=0;i<(int)vec.size();i++) 37 { 38 int nde=vec[i]; 39 while(nde&&vis[nde]) 40 vis[nde]=false,nde=fth[nde]; 41 } 42 } 43 int main() 44 { 45 scanf("%s%d",str+1,&T); 46 lst=tot=1,lth=strlen(str+1); 47 for(int i=1;i<=lth;i++) 48 ori[Insert(str[i]-'a')]=true; 49 while(T--) 50 { 51 scanf("%s%d%d",str+1,&t1,&t2); 52 vec.clear(),lst=1,lth=strlen(str+1); 53 for(int i=1;i<=lth;i++) 54 vec.push_back(Insert(str[i]-'a')); 55 long long ans=0,anss=0; 56 for(int i=0;i<(int)vec.size();i++) 57 { 58 int nde=vec[i]; 59 while(nde&&!vis[nde]) 60 { 61 ans+=len[nde]-len[fth[nde]]; 62 if(ori[nde]) anss+=len[nde]-len[fth[nde]]; 63 vis[nde]=true,nde=fth[nde]; 64 } 65 } 66 printf("%lld ",ans-anss),Clean(); 67 } 68 return 0; 69 }