1 一、后缀数组
2 #define maxn 200015
3 int wa[maxn],wb[maxn],wv[maxn],WS[maxn];
4 int len, sa[maxn] ;
5 inline void swap(int &x, int &y) { int t = x ; x = y ; y = t ; }
6 inline int min(int x, int y) {return x < y ? x : y ; }
7 inline int max(int x, int y) {return x > y ? x : y ; }
8 inline int cmp(int *r,int a,int b,int l) {return r[a]==r[b]&&r[a+l]==r[b+l];}
9 void da(int *r,int *sa,int n,int m){
10 int i,j,p,*x=wa,*y=wb,*t;
11 for(i=0;i<m;i++) WS[i]=0;
12 for(i=0;i<n;i++) WS[x[i]=r[i]]++;
13 for(i=1;i<m;i++) WS[i]+=WS[i-1];
14 for(i=n-1;i>=0;i--) sa[--WS[x[i]]]=i;
15 for(j=1,p=1;p<n;j*=2,m=p)
16 {
17 for(p=0,i=n-j;i<n;i++) y[p++]=i;
18 for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
19 for(i=0;i<n;i++) wv[i]=x[y[i]];
20 for(i=0;i<m;i++) WS[i]=0;
21 for(i=0;i<n;i++) WS[wv[i]]++;
22 for(i=1;i<m;i++) WS[i]+=WS[i-1];
23 for(i=n-1;i>=0;i--) sa[--WS[wv[i]]]=y[i];
24 for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
25 x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
26 }
27 return;
28 }
29 int Rank[maxn], height[maxn];
30 int s[maxn] ;
31 void calheight(int *r,int *sa,int n){
32 int i,j,k=0;
33 for(i=1;i<=n;i++) Rank[sa[i]]=i;
34 for(i=0;i<n;height[Rank[i++]]=k)
35 for(k?k--:0,j=sa[Rank[i]-1];r[i+k]==r[j+k];k++);
36 }int lsa[maxn], tmp[maxn] ;
37 void init_SA(){
38 int i, t ;
39 for(len = 0 ; A[len] ; len ++) s[len] = static_cast<int>(A[len]) ;
40 s[len] = 0 ;
41 da(s, sa, len+1, 259) ;
42 calheight(s, sa, len) ;
43 }
44
45 二、KMP & Manancher
46 1.模板
47 void getNext() {
48 int j = 0 , k = -1 ;
49 next[0] = -1 ;
50 while(j < tl ) // next[i] = max {j | t[i, j] == t[i+1 - j, i] } ;
51 {
52 if(k == -1 || t[j] == t[k] ) next[ ++j] = ++ k ;
53 else k = next[k] ;
54 }
55 }
56 int kmp_Index(){
57 int l = -1, r = sl ;
58 int i = 0 , j = 0 ;
59 while(i < sl && j < tl )
60 {
61 if(j == -1 || s[i] == t[j] )
62 {
63 if(!j ) l = i ;
64 else if(j == tl-1) r = i ;
65 i ++ ; j ++ ;
66 }
67 else j = next[j] ;
68 }
69 printf("%d %d\n", l, r ) ;
70 if(j == tl ) return i - tl ;
71 else return -1 ;
72 }
73 int kmp_Count(){
74 int ans = 0 ;
75 int i, j ;
76 if(sl == 1 && tl == 1)
77 {
78 if(s[0] == t[0] ) return 1 ;
79 else return 0 ;
80 }
81 for(i = 0, j = 0 ; i < sl ; i ++ )
82 {
83 while(j > 0 && s[i] != t[j] ) j = next[j] ;
84 if(s[i] == t[j] ) j ++ ;
85 if(j == tl )
86 {
87 ans ++ ;
88 j = next[j] ; // 提前更新，防治t数组越界 ；
89 }
90 }
91 return ans ;
92 }
93 2.字符串周期
94 int solve(){
95 for(i = 1 ; i <= n ; i ++ ){
96 len = i - next[i] ;
97 if(next[i] && !(i % len ) ) printf("%d %d\n", i , i / len ) ; //
98 }
99 }
100 3.T与S[i,n]的最长公共前缀
101 //extend[i] 数组表示T 与 S[i , n -1] 的最长公共前缀 ；
102 void build_Next(){
103 int k, q, p, a ;
104 next[0] = n ;
105 for (k = 1 , q = -1 ; k < n ; k ++, q --)
106 {
107 if (q < 0 || k + next[k - a] >= p)
108 {
109 if (q < 0 ) q = 0 , p = k ;
110 //q是B串继续向后匹配的指针，p是A串继续向后匹配的指针，
111 也是曾经到达过的最远位置+1
112 //q在每次计算后会减小1，直观的讲就是B串向后错了一位
113 while (p < n && t[p] == t[q]) p ++, q ++ ;
114 next[k] = q, a = k ;
115 }
116 else next[k] = next[k - a] ;
117 }
118 }
119 void extend_KMP(){
120 int k, q, p, a;
121 for (k = 0, q = -1; k < n ; k ++, q --)
122 {
123 if (q < 0 || k + next[k - a] >= p)
124 {
125 if (q < 0) q = 0, p = k ;
126 while (p < n && q < n && s[p] == t[q])
127 {
128 p ++ ;
129 q ++ ;
130 }
131 extend[k] = q ;
132 a = k ;
133 }
134 else extend[k] = next[k - a];
135 }
136 }
137 /*void ExtendKmp(char ss[],int ls,char tt[],int lt){// 直接调用；
138 int i,j,k;
139 int Len,L;
140 j=0;
141 while(tt[j+1]==tt[j]&&j+1<lt) j++;
142 next[1]=j,k=1;
143 for(i=2;i<lt;i++){
144 Len=k+next[k],L=next[i-k];
145 if(Len>L+i) next[i]=L;
146 else{
147 j=Len-i>0?Len-i:0;
148 while(tt[i+j]==tt[j]&&i+j<lt) j++;
149 next[i]=j,k=i;
150 }
151 }
152 j=0;
153 while(ss[j]==tt[j]&&j<lt&&j<ls) j++;
154 extend[0]=j,k=0;
155 for(i=1;i<ls;i++){
156 Len=k+extend[k],L=next[i-k];
157 if(Len>L+i) extend[i]=L;
158 else{
159 j=Len-i>0?Len-i:0;
160 while(ss[i+j]==tt[j]&&i+j<ls&&j<lt) j++;
161 extend[i]=j,k=i;
162 }
163 }
164 } */
165 4.Manancger算法
166 void initStr(){ // 将原字符串a 转化为加了'#'号的字符串 s，
167 // 将问题全转化为“长度都为奇数”的情况；
168 int i , n = strlen(a) ;
169 for(i = 1 ; i <= n ; i ++ )
170 {
171 s[2*i] = a[i-1] ;
172 s[2*i + 1 ] = '#' ;
173 }
174 s[2*i] = '\0' ;
175 }
176 void manacherMaxPali(){
177 int i , mx = 0 , r = 0 , id = 0 , ri ; // mx 表示s[i]前面所有回文字串的最右端 ，
178 for(i = 1 ; i < len ; i ++ )// id 表示取得mx时对应 s 中的位置 ；
179 {// p[i] = min{ p[id - (i-id) ] , mx - i }，求出最小的可能值；
180 if(mx > i ) p[i] = getMin(p[2*id - i ] , mx - i ) ;
181 else p[i] = 1 ;
182 // 检测p[i]能否继续增加 ；
183 for(; s[i - p[i] ] == s[i + p[i] ] ; p[i] ++ ) ;
184 if(i + p[i] > mx ) //更新 mx 及 id ;
185 {
186 mx = i + p[i] ;
187 id = i ;
188 }
189 if(r < p[i] )
190 {
191 r = p[i] ;
192 ri = i ;
193 }
194 }
195 int b = ri - r + 1;
196 for(i = b ; i < ri + r ; i ++ ) if(s[i] != '#' ) printf("%c", s[i]) ;printf("\n") ;
197 }
198 三、AC Automation
199 struct Node{
200 int c ;
201 Node * f, *next[26] ;
202 Node(){
203 memset(next, NULL, sizeof(next)) ;
204 c = 0 ; f = NULL ;
205 }
206 } *que[QMAXN] ;
207 char kw[51], str[MAXN] ;
208 void insert(Node *rt, char s[]){
209 int index, i = 0 ;
210 Node *p = rt ;
211 while(s[i]){
212 index = s[i]-'a' ;
213 if(p->next[index] == NULL) p->next[index] = new Node() ;
214 p = p->next[index] ;
215 i ++ ;
216 }
217 (p->c) ++ ;
218 }
219 void getFail(Node * rt){
220 Node *tmp, *p ;
221 int rear = 0, front = 0 ;
222 rt->f = NULL ;
223 que[rear++] = rt ;
224 while(rear != front){
225 tmp = que[front++] ; //取出已经更新的节点，更新它的所有孩子节点；
226 for(int i = 0 ; i < 26 ; i ++)
227 {
228 if(tmp->next[i] == NULL) continue ;
229 if(tmp == rt) tmp->next[i]->f = rt ;
230 //假设第一层的所有节点fail指针指向根节点；
231 else //如果不是第一层的，则从父节点的失败指针开始找到一个节点p：
232 该节点具有有含有i字符的子节点p->next[i]；
233 { //因为当前指针与p匹配，则其孩子节点就应该p->next[i]匹配；
234 for(p = tmp->f ; p && (p->next[i] == NULL) ; p = p->f) ;
235 tmp->next[i]->f = (p == NULL) ? rt : p->next[i] ;
236 }
237 que[rear++] = tmp->next[i] ; //将已更新的子节点入队列；
238 }
239 }
240 }
241 int query(Node * rt){
242 int i = 0, count = 0, index ;
243 Node *tmp, *p = rt ;
244 while(str[i])
245 {
246 index = str[i] - 'a' ;//如果当前节点不能匹配，且又不是root，则找失败指针；root失败指针为NULL；
247 while(p->next[index] == NULL && p != rt) p = p->f ;
248 p = p->next[index] ; //继续匹配；
249 if(p == NULL) p = rt ; //说明上一轮匹配结束，重新开始匹配；
250 tmp = p ;
251 while(tmp != rt && tmp->c != -1)
252 {
253 count += tmp->c ;
254 tmp->c = -1 ; //说明已经遍历过了；
255 tmp= tmp->f ; //这时，如果tmp失败节点如果是单词结尾的话也要考虑；
256 }
257 i++ ;
258 }
259 return count ;
260 }
261 int solve(){
262 Node * root ;
263 while(T --)
264 {
265 root = new Node() ;
266 scanf("%d", &n) ;
267 for(i = 1 ; i <= n ; i ++){scanf("%s", kw) ;insert(root, kw) ;}
268 getFail(root) ;scanf("%s", str) ;
269 printf("%d\n", query(root)) ;
270 }
271 四、后缀自动机
272 /*****************后缀自动机模板**************************************/
273 const int Smaxn = 26 ; const int maxn = 4010 ;
274 struct node{
275 node *par,*go[Smaxn];
276 int num， val ;
277 }*root,*tail,que[maxn],*top[maxn];
278 int tot, len ;
279 void add(int c,int l){
280 node *p=tail,*np=&que[tot++];
281 np->val=l;
282 while(p&&p->go[c]==NULL)
283 p->go[c]=np,p=p->par;
284 if(p==NULL) np->par=root;
285 else
286 {
287 node *q=p->go[c];
288 if(p->val+1==q->val) np->par=q;
289 else
290 {
291 node *nq=&que[tot++];
292 *nq=*q;
293 nq->val=p->val+1 ;
294 np->par=q->par=nq;
295 while(p&&p->go[c]==q) p->go[c]=nq,p=p->par;
296 }
297 }
298 tail=np;
299 }
300 void init(){
301 memset(que,0,sizeof(que));
302 tot=0 ;
303 len = 1 ;
304 root = tail= &que[tot++] ;
305 }
