先上一份代码……回去研究研究 @Sdchr
READ MORE →
BZOJ2555
后缀自动机+LCT
还没加LCT…… 现在是妥妥的TLE
等下再补LCT上去吧
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 |
#include <cstdio> #include <algorithm> #include <cstring> #include <iostream> #include <cstdlib> #include <cmath> #include <string> #include <map> #define p(x) ('0'<=x&&x<='9') char cc; int C; template <class T> void read( T &x ) { x=0; C=1; cc=getchar(); while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } using namespace std; namespace SAM { int pcnt,last; #define NIL 0 #define root 1 #define N 600010 struct node { // map<int,int> ch; int ch[26]; int fa,len,cnt; // init() { ch.clear();c fa=len,cnt=0; } node init() { memset(ch,0,sizeof(ch)); fa=len=cnt=0; } // int operator [] (const int &x) { if(ch.find(x)) return ch[x]; return 0; } int operator [] (const int &x) { return ch[x]; } }pool[N<<1]; void dododo(int x) { for(;x!=root;x=pool[x].fa) pool[x].cnt++; } void insert(int x) { static int node,p,q,nq; node=++pcnt; p=last; last=node; pool[node].len=pool[p].len+1; for(;!pool[p][x]&&p;p=pool[p].fa) pool[p].ch[x]=node; if(!p) { pool[node].fa=root; dododo(node); return; } q=pool[p][x]; if(pool[q].len==pool[p].len+1) pool[node].fa=q; else { nq=++pcnt; pool[nq]=pool[q]; pool[nq].len=pool[p].len+1; pool[q].fa=pool[node].fa=nq; for(;p&&pool[p][x]==q;p=pool[p].fa)pool[p].ch[x]=nq; } dododo(node); } void insert(string x) { for(unsigned int i=0;i<x.length();i++) insert(x[i]-'A'); } int solve(string x) { static int node; node=root; for(unsigned int i=0;i<x.length();i++) { x[i]-='A'; if(!pool[node][x[i]]) return 0; node=pool[node][x[i]]; } return pool[node].cnt; } void init() { pcnt=last=1; pool[1].init(); } #undef N #undef NIL #undef root } string decode(string s,int mask) { for(unsigned int j=0;j<s.length();j++) { mask=(mask*131+j) % s.length(); char t=s[j]; s[j]=s[mask]; s[mask]=t; } return s; } int main() { SAM::init(); string s,ss; char cmd[10]; int mask=0,m,ans; read(m); cin>>s; SAM::insert(s); for(;m;m--) { scanf("%s",cmd); cin>>s; ss=decode(s,mask); if(cmd[0]=='Q') { ans=SAM::solve(ss); mask^=ans; printf("%d\n",ans); } else SAM::insert(ss); } } |