字符串匹配--最大最小表示法模板

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 const int maxn=1e5+5;
 7 char s[maxn<<1];
 8 
 9 inline int max(int a,int b){return a>b?a:b;}
10 inline int min(int a,int b){return a<b?a:b;}
11 
12 int MINR(char s[],int l){        //s是原串（未加倍过），l是原串长
13     for(int i=0;i<l;++i)s[l+i]=s[i];    //将s串加倍
14     s[2*l]=0;
15     int i=0,j=1;                    //利用i，j指针移动
16     while(i<l&&j<l){
17         int k=0;
18         while(s[i+k]==s[j+k]&&k<l)++k;    //不断比较直到比较完长度为l的串或两个子串不相等
19         if(k==l)return min(i,j);        //若比较出长度为l则直接返回靠前的那个串的开始位置
20         if(s[i+k]>s[j+k])i=max(i+k+1,j+1);    //i串比j串大，那么i到i+k中的串都比j串大，i可以直接移动到i+k+1位置，而起始位置比j小的肯定都在j移动过程中比较过，所以i可以直接移动到j+1位置，因此取这两值的最大值
21         else j=max(j+k+1,i+1);    //同上
22     }
23     return min(i,j);            //返回位置靠前的下标
24 }
25 
26 int MAXR(char s[],int l){
27     for(int i=0;i<l;++i)s[l+i]=s[i];
28     s[2*l]=0;
29     int i=0,j=1;
30     while(i<l&&j<l){
31         int k=0;
32         while(s[i+k]==s[j+k]&&k<l)++k;
33         if(k==l)return min(i,j);
34         if(s[i+k]<s[j+k])i=max(i+k+1,j+1);
35         else j=max(j+k+1,i+1);
36     }
37     return min(i,j);
38 }