题目大意：给出一个字符串，支持在线在字符串后面加一个字符串，查询一个字符串在串中出现过几次。

思路：如果不想写正解的话，这个题就是后缀自动机的简单应用。正解其实是LCT+SAM，但是时间比暴力慢一倍。。。

暴力就很简单了，正序建立后缀自动机，每次查询的时候找到位置直接输出size的值。注意两点，一个是分裂节点的时候，size也要复制过去。查询的时候发现找不到要return 0;

CODE：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define MAX 4000010 using namespace std; struct Complex{ Complex* tranc[26],*father; int len,size; }mempool[MAX],*C = mempool,*last,*root,none,*nil = &none; Complex *NewComplex(int _) { C->len = _; C->size = 0; fill(C->tranc,C->tranc + 26,nil); C->father = nil; return C++; } void Initialize() { root = last = NewComplex(0); } inline void Add(int c) { Complex *np = NewComplex(last->len + 1),*p = last; for(; p != nil && p->tranc[c] == nil; p = p->father) p->tranc[c] = np; if(p == nil) np->father = root; else { Complex *q = p->tranc[c]; if(q->len == p->len + 1) np->father = q; else { Complex *nq = NewComplex(p->len + 1); memcpy(nq->tranc,q->tranc,sizeof(nq->tranc)); nq->father = q->father; np->father = q->father = nq; nq->size = q->size; for(; p != nil && p->tranc[c] == q; p = p->father) p->tranc[c] = nq; } } last = np; for(; np != root; np = np->father) ++np->size; } int asks; char s[MAX],opt[10]; inline void DecodeWithMask(int mask) { int length = strlen(s); for(int i = 0; i < length; ++i) { mask = (mask * 131 + i) % length; swap(s[i],s[mask]); } } inline int Ask() { Complex *now = root; int length = strlen(s); for(int i = 0; i < length; ++i) if(now->tranc[s[i] - 'A'] != nil) now = now->tranc[s[i] - 'A']; else return 0; return now->size; } int main() { Initialize(); scanf("%d%s",&asks,s); int length = strlen(s); for(int i = 0; i < length; ++i) Add(s[i] - 'A'); int mask = 0; for(int i = 1; i <= asks; ++i) { scanf("%s%s",opt,s); DecodeWithMask(mask); if(opt[0] == 'Q') { int last_ans = Ask(); printf("%d\n",last_ans); mask ^= last_ans; } else { length = strlen(s); for(int i = 0; i < length; ++i) Add(s[i] - 'A'); } } return 0; }