练习后缀数组-白红宇

练习后缀数组

阅读量：5135 次

发布时间：2019-06-13

本文共 27553 字，大约阅读时间需要 91 分钟。

一.字符串公共子串

要求尽量相同，那么将各个子串连在一起用‘#’连接，查最长height，判一下sa位置就好了

代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 using std::max; 5 using std::min; 6 using std::swap; 7 const int N=1000000; 8 int tmr[N]; 9 int rnk[N];10 int has[N];11 int hgt[N];12 int sa[N];13 int ln[N];14 char str[N];15 int n,cnt;16 int len;17 int ans;18 bool Same(int a,int b,int l)19 {20     if(a+l>len||b+l>len)21         return false;22     return (rnk[a]==rnk[b])&&(rnk[a+l]==rnk[b+l]);23 }24 int main()25 {26     scanf("%s",str+1);27     int len1=strlen(str+1);28     for(len=1;len<=len1;len++)29         ln[len]=str[len];30     scanf("%s",str+1);31     ln[++len]='#';32     int len2=strlen(str+1);33     for(int i=1;i<=len2;i++)34         ln[++len]=str[i];35     for(int i=1;i<=len;i++)36         has[ln[i]]++;37     for(int i=0;i<128;i++)38         if(has[i])39             tmr[i]=++cnt;40     for(int i=1;i<128;i++)41         has[i]+=has[i-1];42     for(int i=1;i<=len;i++)43     {44         sa[has[ln[i]]--]=i;45         rnk[i]=tmr[ln[i]];46     }47     for(int k=1;cnt!=len;k<<=1)48     {49         cnt=0;50         for(int i=0;i<=len;i++)51             has[i]=0;52         for(int i=1;i<=len;i++)53             has[rnk[i]]++;54         for(int i=1;i<=len;i++)55             has[i]+=has[i-1];56         for(int i=len;i;i--)57             if(sa[i]>k)58                 tmr[sa[i]-k]=has[rnk[sa[i]-k]]--;59         for(int i=1;i<=k;i++)60             tmr[len-i+1]=has[rnk[len-i+1]]--;61         for(int i=1;i<=len;i++)62             sa[tmr[i]]=i;63         for(int i=1;i<=len;i++)64             if(Same(sa[i],sa[i-1],k))65                 tmr[sa[i]]=cnt;66             else67                 tmr[sa[i]]=++cnt;68         for(int i=1;i<=len;i++)    69             rnk[i]=tmr[i];70     }71     hgt[1]=0;72     for(int i=1;i<=len;i++)73     {74         if(rnk[i]==1)    75             continue;76         int j=max(1,hgt[rnk[i-1]]-1);77         while(ln[i+j-1]==ln[sa[rnk[i]-1]+j-1])78             hgt[rnk[i]]=j++;79     }80     for(int i=2;i<=len;i++)81     {82         if(hgt[i]>ans)83         {84             int a=sa[i];85             int b=sa[i-1];86             if(a>b)87                 swap(a,b);88             if(a<=len1&&b>len1+1)89                 ans=hgt[i];90         }91     }92     printf("%d\n",ans);93     return 0;94 }

2.可重复可不对齐公共子串个数。

同理，在两个字符串中间加一个‘#’连在一起。

查询hgt，显然，小于hgt的值都能取到，那么就单调栈优化一下。

理论上是双单调栈，但做两次也是一样的。

代码：

1 #include
     
        2 #include
      
         3 #include
       
          4 typedef long long lnt;  5 const int N=200005;  6 int tmr[N];  7 int rnk[N];  8 int has[N];  9 int hgt[N]; 10 int sa[N]; 11 int str[N]; 12 lnt s[N]; 13 lnt n[N]; 14 char tmp[N]; 15 int len; 16 int cnt; 17 int tt; 18 int tp; 19 bool Same(int a,int b,int l) 20 { 21     if(a+l>len||b+l>len) 22         return false; 23     return (rnk[a]==rnk[b])&&(rnk[a+l]==rnk[b+l]); 24 } 25 void Gsa(void) 26 { 27     memset(sa,0,sizeof(sa)); 28     memset(has,0,sizeof(has)); 29     memset(hgt,0,sizeof(hgt)); 30     memset(tmr,0,sizeof(tmr)); 31     cnt=0; 32     for(int i=1;i<=len;i++) 33         has[str[i]]++; 34     for(int i=0;i<128;i++) 35         if(has[i]) 36             tmr[i]=++cnt; 37     for(int i=1;i<128;i++) 38         has[i]+=has[i-1]; 39     for(int i=1;i<=len;i++) 40     { 41         sa[has[str[i]]--]=i; 42         rnk[i]=tmr[str[i]]; 43     } 44     for(int k=1;cnt!=len;k<<=1) 45     { 46         cnt=0; 47         for(int i=0;i<=len;i++) 48             has[i]=0; 49         for(int i=1;i<=len;i++) 50             has[rnk[i]]++; 51         for(int i=1;i<=len;i++) 52             has[i]+=has[i-1]; 53         for(int i=len;i;i--) 54             if(sa[i]>k) 55                 tmr[sa[i]-k]=has[rnk[sa[i]-k]]--; 56         for(int i=1;i<=k;i++) 57             tmr[len-i+1]=has[rnk[len-i+1]]--; 58         for(int i=1;i<=len;i++) 59             sa[tmr[i]]=i; 60         for(int i=1;i<=len;i++) 61             if(Same(sa[i],sa[i-1],k)) 62                 tmr[sa[i]]=cnt; 63             else 64                 tmr[sa[i]]=++cnt; 65         for(int i=1;i<=len;i++) 66             rnk[i]=tmr[i]; 67     } 68     return ; 69 } 70 void Ght(void) 71 { 72     for(int i=1;i<=len;i++) 73     { 74         if(rnk[i]==1) 75             continue; 76         int j=std::max(1,hgt[rnk[i-1]]-1); 77         while(str[i+j-1]==str[sa[rnk[i]-1]+j-1]) 78             hgt[rnk[i]]=j++; 79     } 80     return ; 81 } 82 int main() 83 { 84     while(1) 85     { 86         tp=0; 87         memset(str,0,sizeof(str)); 88         len=0; 89         scanf("%d",&tt); 90         if(!tt) 91             return 0; 92         scanf("%s",tmp+1); 93         int len1=strlen(tmp+1); 94         for(int i=1;i<=len1;i++) 95             str[++len]=tmp[i]; 96         str[++len]='#'; 97         scanf("%s",tmp+1); 98         int len2=strlen(tmp+1); 99         for(int i=1;i<=len2;i++)100             str[++len]=tmp[i];101         Gsa();102         Ght();103         lnt ans=0;104         lnt sum=0;105         tp=0;106         for(int i=2;i<=len;i++)107         {108             if(hgt[i]
        
         len1+1)130                 ans+=sum;131         }132         sum=0;133         tp=0;134         for(int i=2;i<=len;i++)135         {136             if(hgt[i]
         
          len1+1)153             {154                 sum+=(lnt)(s[tp]-tt+1);155                 n[tp]++;156             }157             if(sa[i]<=len1)158                 ans+=sum;159         }160         printf("%lld\n",ans);161     }162     return 0;163 }

二.二分check height数组

1.找最长重复子串

同一串中最长字串（要求不重叠）

二分答案，字典序相近后缀的前缀更趋向于相同。

查询时注意开始位置使其不重叠。

我不会告诉你我数组没清零WA了N次

代码：

1 #include
     
        2 #include
      
         3 #include
       
          4 using std::max;  5 using std::min;  6 int thm[500000];  7 int rnk[500000];  8 int has[500000];  9 int tmr[500000]; 10 int hgt[500000]; 11 int sa[500000]; 12 int n; 13 int cnt; 14 bool Same(int a,int b,int l) 15 { 16     if(a+l>n||b+l>n) 17         return false; 18     return (rnk[a]==rnk[b])&&(rnk[a+l]==rnk[b+l]); 19 } 20 bool check(int l) 21 { 22     int mx=-0x3f3f3f3f; 23     int mn=0x3f3f3f3f; 24     for(int i=2;i<=n;i++) 25     { 26         if(hgt[i]>=l) 27         { 28             mx=max(mx,max(sa[i],sa[i-1])); 29             mn=min(mn,min(sa[i],sa[i-1])); 30             if(mx-mn>l) 31                 return true; 32         }else{ 33             mx=-0x3f3f3f3f; 34             mn=0x3f3f3f3f; 35         } 36     } 37     return false; 38 } 39 int main() 40 { 41     while(scanf("%d",&n)!=EOF) 42     { 43         if(!n) 44             return 0; 45         memset(thm,0,sizeof(thm)); 46         memset(rnk,0,sizeof(rnk)); 47         memset(has,0,sizeof(has)); 48         memset(tmr,0,sizeof(tmr)); 49         memset(hgt,0,sizeof(hgt)); 50         memset(sa,0,sizeof(sa)); 51         for(int i=1;i<=n;i++) 52         { 53             scanf("%d",&thm[i]); 54             has[i]=0; 55         } 56         n--; 57         cnt=0; 58         for(int i=1;i<=n;i++) 59             thm[i]=thm[i+1]-thm[i]+88; 60         thm[n+1]=0; 61         for(int i=1;i<=n;i++) 62             has[thm[i]]++; 63         for(int i=0;i<=200;i++) 64             if(has[i]) 65                 tmr[i]=++cnt; 66         for(int i=1;i<=200;i++) 67             has[i]+=has[i-1]; 68         for(int i=1;i<=n;i++) 69         { 70             sa[has[thm[i]]--]=i; 71             rnk[i]=tmr[thm[i]]; 72         } 73         for(int k=1;cnt!=n;k<<=1) 74         { 75             cnt=0; 76             for(int i=1;i<=n;i++) 77                 has[i]=0; 78             for(int i=1;i<=n;i++) 79                 has[rnk[i]]++; 80             for(int i=1;i<=n;i++) 81                 has[i]+=has[i-1]; 82             for(int i=n;i;i--) 83                 if(sa[i]>k) 84                     tmr[sa[i]-k]=has[rnk[sa[i]-k]]--; 85             for(int i=1;i<=k;i++) 86                 tmr[n-i+1]=has[rnk[n-i+1]]--; 87             for(int i=1;i<=n;i++) 88                 sa[tmr[i]]=i; 89             for(int i=1;i<=n;i++) 90                 if(Same(sa[i],sa[i-1],k)) 91                     tmr[sa[i]]=cnt; 92                 else 93                     tmr[sa[i]]=++cnt; 94             for(int i=1;i<=n;i++) 95                 rnk[i]=tmr[i]; 96         } 97         hgt[1]=0; 98         for(int i=1;i<=n;i++) 99         {100             if(rnk[i]==1)101                 continue;102             int j=max(1,hgt[rnk[i-1]]-1);103             while(thm[j+i-1]==thm[sa[rnk[i]-1]+j-1])104                 hgt[rnk[i]]=j++;105         }106         int ans=0;107         int l=0,r=n;108         while(l<=r)109         {110             int mid=(l+r)>>1;111             if(check(mid))112             {113                 ans=mid;114                 l=mid+1;115             }else116                 r=mid-1;117         }118         if(ans>=4)119             printf("%d\n",ans+1);120         else121             puts("0");122     }123     return 0;124 }

2.找重复次数大于K的子串，可重叠

二分答案，找连续height大于K的即可。

代码：

1 #include
     
        2 #include
      
         3 #include
       
          4 using std::max;  5 using std::min;  6 const int N=2000000;  7 int tmr[N];  8 int rnk[N];  9 int has[N]; 10 int hgt[N]; 11 int qlt[N]; 12 int sa[N]; 13 int n,K; 14 int cnt; 15 int ans; 16 bool Same(int a,int b,int l) 17 { 18     if(a+l>n||b+l>n) 19         return false; 20     return (rnk[a]==rnk[b])&&(rnk[a+l]==rnk[b+l]); 21 } 22 bool check(int l) 23 { 24     cnt=1; 25     for(int i=2;i<=n;i++) 26     { 27         if(hgt[i]>=l) 28         { 29             cnt++; 30             if(cnt>=K) 31                 return true; 32         }else 33             cnt=1; 34     } 35     return false; 36 } 37 int main() 38 { 39     scanf("%d%d",&n,&K); 40     for(int i=1;i<=n;i++) 41         scanf("%d",&qlt[i]); 42     for(int i=1;i<=n;i++) 43         has[qlt[i]]++; 44     for(int i=0;i<=1000000;i++) 45         if(has[i]) 46             tmr[i]=++cnt; 47     for(int i=1;i<=1000000;i++) 48         has[i]+=has[i-1]; 49     for(int i=1;i<=n;i++) 50     { 51         sa[has[qlt[i]]--]=i; 52         rnk[i]=tmr[qlt[i]]; 53     } 54     for(int k=1;cnt!=n;k<<=1) 55     { 56         cnt=0; 57         for(int i=0;i<=n;i++) 58             has[i]=0; 59         for(int i=1;i<=n;i++) 60             has[rnk[i]]++; 61         for(int i=1;i<=n;i++) 62             has[i]+=has[i-1]; 63         for(int i=n;i;i--) 64             if(sa[i]>k) 65                 tmr[sa[i]-k]=has[rnk[sa[i]-k]]--; 66         for(int i=1;i<=k;i++) 67             tmr[n-i+1]=has[rnk[n-i+1]]--; 68         for(int i=1;i<=n;i++) 69             sa[tmr[i]]=i; 70         for(int i=1;i<=n;i++) 71             if(Same(sa[i],sa[i-1],k)) 72                 tmr[sa[i]]=cnt; 73             else 74                 tmr[sa[i]]=++cnt; 75         for(int i=1;i<=n;i++) 76             rnk[i]=tmr[i]; 77     } 78     hgt[1]=0; 79     for(int i=1;i<=n;i++) 80     { 81         if(rnk[i]==1) 82             continue; 83         int j=max(1,hgt[rnk[i-1]]-1); 84         while(qlt[i+j-1]==qlt[sa[rnk[i]-1]+j-1]) 85             hgt[rnk[i]]=j++; 86     } 87     int l=0,r=n; 88     while(l<=r) 89     { 90         int mid=(l+r)>>1; 91         if(check(mid)) 92         { 93             ans=mid; 94             l=mid+1; 95         }else 96             r=mid-1; 97     } 98     printf("%d\n",ans); 99     return 0;100 }

3.找字符串中连续出现x次子串。

二分答案，查询hgt连续大于某个值。

注意要用不同未出现连字符连接否则会被进行比较。

一共26个字母，100个串，可利用字符比较紧（我是不是傻，为啥不用数字）

把字母压到前面，利用后面的字符就好了。

注意存储最好用第一个（因为我闲的233）

代码：

1 #include
     
        2 #include
      
         3 #include
       
          4 const int N=200000;  5 int tmr[N];  6 int rnk[N];  7 int has[N];  8 int hgt[N];  9 int sa[N]; 10 int str[N]; 11 char tmp[N]; 12 int len; 13 int l[10000]; 14 bool vis[200]; 15 int blg[N]; 16 int cnt; 17 int n; 18 int sum; 19 int ret[N]; 20 bool Same(int a,int b,int l) 21 { 22     if(a+l>len||b+l>len) 23         return false; 24     return (rnk[a]==rnk[b])&&(rnk[a+l]==rnk[b+l]); 25 } 26 void Gsa(void) 27 { 28     memset(tmr,0,sizeof(tmr)); 29     memset(rnk,0,sizeof(rnk)); 30     memset(has,0,sizeof(has)); 31     memset(hgt,0,sizeof(hgt)); 32     cnt=0; 33     for(int i=1;i<=len;i++) 34         has[str[i]]++; 35     for(int i=0;i<128;i++) 36         if(has[i]) 37             tmr[i]=++cnt; 38     for(int i=1;i<128;i++) 39         has[i]+=has[i-1]; 40     for(int i=1;i<=len;i++) 41     { 42         sa[has[str[i]]--]=i; 43         rnk[i]=tmr[str[i]]; 44     } 45     for(int k=1;cnt!=len;k<<=1) 46     { 47         cnt=0; 48         for(int i=0;i<=len;i++) 49             has[i]=0; 50         for(int i=1;i<=len;i++) 51             has[rnk[i]]++; 52         for(int i=1;i<=len;i++) 53             has[i]+=has[i-1]; 54         for(int i=len;i;i--) 55             if(sa[i]>k) 56                 tmr[sa[i]-k]=has[rnk[sa[i]-k]]--; 57         for(int i=1;i<=k;i++) 58             tmr[len-i+1]=has[rnk[len-i+1]]--; 59         for(int i=1;i<=len;i++) 60             sa[tmr[i]]=i; 61         for(int i=1;i<=len;i++) 62             if(Same(sa[i],sa[i-1],k)) 63                 tmr[sa[i]]=cnt; 64             else 65                 tmr[sa[i]]=++cnt; 66         for(int i=1;i<=len;i++) 67             rnk[i]=tmr[i]; 68     } 69     return ; 70 } 71 void Ght(void) 72 { 73     for(int i=1;i<=len;i++) 74     { 75         if(rnk[i]==1) 76             continue; 77         int j=std::max(1,hgt[rnk[i-1]]-1); 78         while(str[i+j-1]==str[sa[rnk[i]-1]+j-1]) 79             hgt[rnk[i]]=j++; 80     } 81     return ; 82 } 83 bool can(int x) 84 { 85     int ans=0; 86     int num=0; 87     memset(vis,0,sizeof(vis)); 88     int bgn=1; 89     for(int i=2;i<=len;i++) 90     { 91         if(hgt[i]>=x) 92         { 93             if(!vis[blg[sa[i-1]]]&&blg[sa[i-1]]) 94             { 95                 ans++; 96                 vis[blg[sa[i-1]]]=true; 97             } 98             if(!vis[blg[sa[i]]]&&blg[sa[i]]) 99             {100                 ans++;101                 vis[blg[sa[i]]]=true;102             }103         }else{104             if(ans>n/2)105                 ret[++num]=sa[bgn];106             ans=0;107             bgn=i;108             memset(vis,0,sizeof(vis));109         }110     }111     if(ans>n/2)112         ret[++num]=sa[len];113     if(num)114     {115         sum=num;116         return true;117     }118     return false;119 }120 int main()121 {122     while(1)123     {124         len=0;125         sum=0;126         memset(str,0,sizeof(str));127         scanf("%d",&n);128         if(!n)129             return 0;130         for(int i=1;i<=n;i++)131         {132             scanf("%s",tmp+1);133             l[i]=strlen(tmp+1);134             for(int j=1;j<=l[i];j++)135             {136                 str[++len]=tmp[j]-'a';137                 blg[len]=i;138             }139             l[i]=len;140             str[++len]=26+i;141             blg[len]=0;142         }143         Gsa();144         Ght();145         int l=0;146         int r=len;147         int lth=0;148         while(l<=r)149         {150             int mid=(l+r)>>1;151             if(can(mid))152             {153                 lth=mid;154                 l=mid+1;155             }else156                 r=mid-1;157         }158         if(l<=1)159             puts("?");160         else{161             for(int i=1;i<=sum;i++)162             {163                 for(int j=0;j

4.最长复现式公共子串。

用不同符号连接在一起。

二分查找check max-min>长度即可。

代码：

1 #include
     
        2 #include
      
         3 #include
       
          4 const int N=200000;  5 int tmr[N];  6 int rnk[N];  7 int has[N];  8 int hgt[N];  9 int sa[N]; 10 int mn[20]; 11 int mx[20]; 12 int str[N]; 13 bool vis[20]; 14 int blg[N]; 15 char tmp[N]; 16 int len; 17 int cnt; 18 int n; 19 bool Same(int a,int b,int l) 20 { 21     if(a+l>len||b+l>len) 22         return false; 23     return (rnk[a]==rnk[b])&&(rnk[a+l]==rnk[b+l]); 24 } 25 void Gsa(void) 26 { 27     for(int i=1;i<=len;i++) 28         has[str[i]]++; 29     for(int i=0;i<=200;i++) 30         if(has[i]) 31             tmr[i]=++cnt; 32     for(int i=1;i<=200;i++) 33         has[i]+=has[i-1]; 34     for(int i=1;i<=len;i++) 35     { 36         sa[has[str[i]]--]=i; 37         rnk[i]=tmr[str[i]]; 38     } 39     for(int k=1;cnt!=len;k<<=1) 40     { 41         cnt=0; 42         for(int i=0;i<=len;i++) 43             has[i]=0; 44         for(int i=1;i<=len;i++) 45             has[rnk[i]]++; 46         for(int i=1;i<=len;i++) 47             has[i]+=has[i-1]; 48         for(int i=len;i;i--) 49             if(sa[i]>k) 50                 tmr[sa[i]-k]=has[rnk[sa[i]-k]]--; 51         for(int i=1;i<=k;i++) 52             tmr[len-i+1]=has[rnk[len-i+1]]--; 53         for(int i=1;i<=len;i++) 54             sa[tmr[i]]=i; 55         for(int i=1;i<=len;i++) 56             if(Same(sa[i],sa[i-1],k)) 57                 tmr[sa[i]]=cnt; 58             else 59                 tmr[sa[i]]=++cnt; 60         for(int i=1;i<=len;i++) 61             rnk[i]=tmr[i]; 62     } 63     return ; 64 } 65 void Ght(void) 66 { 67     for(int i=1;i<=len;i++) 68     { 69         if(rnk[i]==1) 70             continue; 71         int j=std::max(1,hgt[rnk[i-1]]-1); 72         while(str[i+j-1]==str[sa[rnk[i]-1]+j-1]) 73             hgt[rnk[i]]=j++; 74     } 75     return ; 76 } 77 void res(void) 78 { 79     for(int i=1;i<=n;i++) 80     { 81         vis[i]=0; 82         mx[i]=-0x3f3f3f3f; 83         mn[i]=0x3f3f3f3f; 84     } 85     return ; 86 } 87 bool check(int x) 88 { 89     for(int i=1;i<=n;i++) 90     { 91         if(mx[i]-mn[i]
        
         =x)102         {103             mx[blg[sa[i]]]=std::max(sa[i],mx[blg[sa[i]]]);104             mx[blg[sa[i-1]]]=std::max(sa[i-1],mx[blg[sa[i-1]]]);105             mn[blg[sa[i]]]=std::min(sa[i],mn[blg[sa[i]]]);106             mn[blg[sa[i-1]]]=std::min(sa[i-1],mn[blg[sa[i-1]]]);107             if(check(x))108                 return true;109         }else{110             res();111         }112     }113     return check(x);114 }115 int main()116 {117     int T;118     scanf("%d",&T);119     while(T--)120     {121         memset(tmr,0,sizeof(tmr));122         memset(has,0,sizeof(rnk));123         memset(hgt,0,sizeof(hgt));124         memset(str,0,sizeof(str));125         memset(blg,0,sizeof(blg));126         len=cnt=0;127         scanf("%d",&n);128         for(int i=1;i<=n;i++)129         {130             scanf("%s",tmp+1);131             int lx=strlen(tmp+1);132             for(int j=1;j<=lx;j++)133             {134                 len++;135                 blg[len]=i;136                 str[len]=tmp[j];137             }138             str[++len]=i+128;139         }140         Gsa();141         Ght();142         int l=0;143         int r=len;144         int ans=0;145         while(l<=r)146         {147             int mid=(l+r)>>1;148             if(can(mid))149             {150                 l=mid+1;151                 ans=mid;152             }else153                 r=mid-1;154         }155         printf("%d\n",ans);156     }157     return 0;158 }

三.相同串个数

不同串个数，这里是求相同串的个数再使用容斥。

因为开始地方不同可以判定相同串就是对height求和

容斥一下，一个串共有len*(len+1)/2

代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 using std::min; 5 using std::max; 6 const int N=1005; 7 int tmr[N]; 8 int rnk[N]; 9 int has[N];10 int hgt[N];11 int sa[N];12 char str[N];13 int T;14 int len;15 int cnt;16 int sum;17 bool Same(int a,int b,int l)18 {19     if(a+l>len||b+l>len)20         return false;21     return (rnk[a]==rnk[b])&&(rnk[a+l]==rnk[b+l]);22 }23 int main()24 {25     scanf("%d",&T);26     while(T--)27     {28         cnt=0;29         memset(tmr,0,sizeof(tmr));30         memset(rnk,0,sizeof(rnk));31         memset(has,0,sizeof(has));32         memset(hgt,0,sizeof(hgt));33         memset(sa,0,sizeof(sa));34         len=0;35         sum=0;36         scanf("%s",str+1);37         len=strlen(str+1);38         for(int i=1;i<=len;i++)39             has[str[i]]++;40         for(int i=0;i<128;i++)41             if(has[i])42                 tmr[i]=++cnt;43         for(int i=1;i<128;i++)44             has[i]+=has[i-1];45         for(int i=1;i<=len;i++)46         {47             sa[has[str[i]]--]=i;48             rnk[i]=tmr[str[i]];49         }50         for(int k=1;cnt!=len;k<<=1)51         {52             cnt=0;53             for(int i=0;i<=len;i++)    54                 has[i]=0;55             for(int i=1;i<=len;i++)56                 has[rnk[i]]++;57             for(int i=1;i<=len;i++)58                 has[i]+=has[i-1];59             for(int i=len;i;i--)60                 if(sa[i]>k)61                     tmr[sa[i]-k]=has[rnk[sa[i]-k]]--;62             for(int i=1;i<=k;i++)63                 tmr[len-i+1]=has[rnk[len-i+1]]--;64             for(int i=1;i<=len;i++)65                 sa[tmr[i]]=i;66             for(int i=1;i<=len;i++)67                 if(Same(sa[i],sa[i-1],k))68                     tmr[sa[i]]=cnt;69                 else70                     tmr[sa[i]]=++cnt;71             for(int i=1;i<=len;i++)72                 rnk[i]=tmr[i];73         }74         for(int i=1;i<=len;i++)75         {76             if(rnk[i]==1)77                 continue;78             int j=max(1,hgt[rnk[i-1]]-1);79             while(str[i+j-1]==str[sa[rnk[i]-1]+j-1])80                 hgt[rnk[i]]=j++;81         }82         for(int i=2;i<=len;i++)83             sum+=hgt[i];84         int ans=((len+1)*len/2)-sum;85         printf("%d\n",ans);86     }87     return 0;88 }

四、rmq预处理获得相同前缀

1.判断回文串：

用倍增法事件复杂度不如manacher

判断一个串正着念反着念，以一个为中心答案。

先预判奇偶性。

代码：

1 #include
     
        2 #include
      
         3 #include
       
          4 using std::max;  5 using std::min;  6 const int N=10000;  7 int tmr[N];  8 int rnk[N];  9 int hgt[20][N]; 10 int has[N]; 11 int sa[N]; 12 int str[N]; 13 int lg[N]; 14 int ln; 15 int cnt; 16 int len; 17 char st[N]; 18 bool Same(int a,int b,int l) 19 { 20     if(a+l>len||b+l>len) 21         return false; 22     return (rnk[a]==rnk[b])&&(rnk[a+l]==rnk[b+l]); 23 } 24 void Gsa(void) 25 { 26     cnt=0; 27     for(int i=1;i<=len;i++) 28         has[str[i]]++; 29     for(int i=0;i<=128;i++) 30         if(has[i]) 31             tmr[i]=++cnt; 32     for(int i=1;i<=128;i++) 33         has[i]+=has[i-1]; 34     for(int i=1;i<=len;i++) 35     { 36         sa[has[str[i]]--]=i; 37         rnk[i]=tmr[str[i]]; 38     } 39     for(int k=1;cnt!=len;k<<=1) 40     { 41         cnt=0; 42         for(int i=0;i<=len;i++) 43             has[i]=0; 44         for(int i=1;i<=len;i++) 45             has[rnk[i]]++; 46         for(int i=1;i<=len;i++) 47             has[i]+=has[i-1]; 48         for(int i=len;i;i--) 49             if(sa[i]>k) 50                 tmr[sa[i]-k]=has[rnk[sa[i]-k]]--; 51         for(int i=1;i<=k;i++) 52             tmr[len-i+1]=has[rnk[len-i+1]]--; 53         for(int i=1;i<=len;i++) 54             sa[tmr[i]]=i; 55         for(int i=1;i<=len;i++) 56             if(Same(sa[i],sa[i-1],k)) 57                 tmr[sa[i]]=cnt; 58             else 59                 tmr[sa[i]]=++cnt; 60         for(int i=1;i<=len;i++) 61             rnk[i]=tmr[i]; 62     } 63 } 64 void Hgt(void) 65 { 66     hgt[0][1]=0; 67     for(int i=1;i<=len;i++) 68     { 69         if(rnk[i]==1) 70             continue; 71         int j=max(1,hgt[0][rnk[i-1]]-1); 72         while(str[i+j-1]==str[sa[rnk[i]-1]+j-1]&&j<=len) 73             hgt[0][rnk[i]]=j++; 74     } 75     for(int i=1;i<=18;i++) 76         for(int j=1;j+(1<
        
         <=len;j++) 77             hgt[i][j]=min(hgt[i-1][j],hgt[i-1][j+(1<<(i-1))]); 78     return ; 79 } 80 int Min(int a,int b) 81 { 82     int l=lg[b-a+1]; 83     return min(hgt[l][a],hgt[l][b-(1<
         
          len||y>len) 88         return 0; 89     int a=min(rnk[x],rnk[y]); 90     int b=max(rnk[x],rnk[y]); 91     return Min(a+1,b); 92 } 93 int main() 94 { 95     for(int i=2;i<=9000;i++) 96         lg[i]=lg[i/2]+1; 97     while(scanf("%s",st+1)!=EOF) 98     { 99         memset(has,0,sizeof(has));100         memset(tmr,0,sizeof(tmr));101         memset(sa,0,sizeof(sa));102         memset(hgt,0,sizeof(hgt));103         memset(str,0,sizeof(str));104         len=0;105         ln=strlen(st+1);106         for(int i=1;i<=ln;i++)107             str[++len]=st[i];108         str[++len]='#';109         for(int i=ln;i;i--)110             str[++len]=st[i];111         Gsa();112         Hgt();113         int sta=1;114         int ans=1;115         for(int i=1;i<=len;i++)116         {117             int tmp=lcp(i,len-i+1);118             if(tmp*2-1>ans)119             {120                 ans=tmp*2-1;121                 sta=i-tmp+1;122             }123             tmp=lcp(i,len-i+2);124             if(tmp*2>ans)125             {126                 ans=tmp*2;127                 sta=i-tmp;128             }129         }130         for(int i=0;i

2.寻找最长连续子串

求出rmq，枚举局部的连续长度。

枚举起始点，在起始点向前扩展，更新答案。

代码：

1 #include
     
        2 #include
      
         3 #include
       
          4 const int N=100000;  5 int tmr[N];  6 int has[N];  7 int rnk[N];  8 int hgt[20][N];  9 int sa[N]; 10 int lg[N]; 11 char str[N]; 12 int len; 13 int cnt; 14 bool Same(int a,int b,int l) 15 { 16     if(a+l>len||b+l>len) 17         return false; 18     return (rnk[a]==rnk[b])&&(rnk[a+l]==rnk[b+l]); 19 } 20 void Gsa(void) 21 { 22     cnt=0; 23     memset(has,0,sizeof(has)); 24     memset(tmr,0,sizeof(tmr)); 25     memset(hgt,0,sizeof(hgt)); 26     for(int i=1;i<=len;i++) 27         has[str[i]]++; 28     for(int i=0;i<128;i++) 29         if(has[i]) 30             tmr[i]=++cnt; 31     for(int i=1;i<128;i++) 32         has[i]+=has[i-1]; 33     for(int i=1;i<=len;i++) 34     { 35         sa[has[str[i]]--]=i; 36         rnk[i]=tmr[str[i]]; 37     } 38     for(int k=1;cnt!=len;k<<=1) 39     { 40         cnt=0; 41         for(int i=0;i
        
         k) 49                 tmr[sa[i]-k]=has[rnk[sa[i]-k]]--; 50         for(int i=1;i<=k;i++) 51             tmr[len-i+1]=has[rnk[len-i+1]]--; 52         for(int i=1;i<=len;i++) 53             sa[tmr[i]]=i; 54         for(int i=1;i<=len;i++) 55             if(Same(sa[i],sa[i-1],k)) 56                 tmr[sa[i]]=cnt; 57             else 58                 tmr[sa[i]]=++cnt; 59         for(int i=1;i<=len;i++) 60             rnk[i]=tmr[i]; 61     } 62 } 63 void Ght(int *h) 64 { 65     h[1]=0; 66     for(int i=1;i<=len;i++) 67     { 68         if(rnk[i]==1) 69             continue; 70         int j=std::max(1,h[rnk[i-1]]-1); 71         while(str[i+j-1]==str[sa[rnk[i]-1]+j-1]) 72             h[rnk[i]]=j++; 73     } 74     return ; 75 } 76 void Grmq(void) 77 { 78     for(int i=1;i<=19;i++) 79         for(int j=1;j+(1<
         
          <=len;j++) 80             hgt[i][j]=std::min(hgt[i-1][j],hgt[i-1][j+(1<<(i-1))]); 81     return ; 82 } 83 void Init(void) 84 { 85     Gsa(); 86     Ght(hgt[0]); 87     Grmq(); 88     return ; 89 } 90 int rmQ(int x,int y) 91 { 92     if(x>y) 93         std::swap(x,y); 94     int l=lg[y-x+1]; 95     return std::min(hgt[l][x],hgt[l][y-(1<
          
           y)102 std::swap(x,y);103 return rmQ(x+1,y);104 }105 int main()106 {107 int tttttttt=0;108 for(int i=2;i
           
            0&&str[s*ln-pre+1]==str[(s+1)*ln-pre+1])129 {130 tmp++;131 if(tmp%ln==0||rnk[tpl]>rnk[s*ln-pre+1])132 tpl=s*ln-pre+1;133 pre++;134 }135 if(lns<(tmp/ln+1)||(lns==(tmp/ln+1)&&rnk[sta]>rnk[tpl]))136 {137 sta=tpl;138 lns=tmp/ln+1;139 ans=lns*ln;140 }141 }142 }143 printf("Case %d: ",tttttttt);144 for(int i=sta;i