acm-字符串整理

  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
", 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
", 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] = '' ;
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("
") ;
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
", 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 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/xieyue/p/4332354.html