后缀数组题目-白红宇

后缀数组题目

阅读量：5261 次

发布时间：2019-06-14

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

hdu 3948

1 /*  2 题意：给你一个串，求该串的不同子回文串的个数；  3   4 分析：首先我们想一下一个比较简单的问，求一个串的不同子串的个数  5 显然每个子串都是一个后缀的前缀，那么只要按照SA[]统计该后缀i的前缀  6 有那些是出现过的，也就是ans+=len[该后缀长]-height[i];  7   8   9 同样的道理，我们先统计出以i为中心的回文串到最右边的距离，然后 10 再统计不同回文串的个数，即减去相同回文串的个数，但是两者还是有区别的 11 其次,为了统一奇偶的差别，我们构造出另一个字符串， 12 s1=aabaa  -> s=$#a#a#b#a#a#  （可以参看本博客前前篇文章MANACHER）  13 首先我用MANACHER的预处理出以s[i]为中心的回文串到最右边的距离记录在lc[i]; 14 当然可以直接用后缀数组的方法求出（将反串加在原串后面，然后询问后缀i和后缀2*n-i的LCP，但要分奇偶） 15  16 统计不同子串个数和统计不同回文串的个数的区别 17 看样例：aabaa 18  19  20 构造的串：$#a#a#b#a#a# 21 后缀  lc[i]        回文串的个数      22 11    1    #            1 23 9     3    #a#           3         24 7     1    #a#a#        1      25 1     1    #a#a#b#a#a#    1         26 3     3    #a#b#a#a#    3    &  27 5     1    #b#a#a#        1 28                      29 0     1    $#a#a#b#a#a#    1 30 10    2    a#            2 31 8     2    a#a#        2 32 2     2    a#a#b#a#a#    2 33 4     2    a#b#a#a#        2 34 6     6    b#a#a#        6 35  36 先不考虑加入#后产生的回文串， 37 在统计后缀3中包含的回文串时，会把#a,和#a#统计进去，但我们发现在统计后缀9时#a,#a#就已经被统计了 38 也就是说统计后缀i中已经被统计过的回文串的个数，不一定只是后缀i-1中的回文，还有可能是更前面的， 39 所以我们在遍历的过程中设置一个标记tmp，表示以字符i为中点能延伸的最长距离，而不是该串在原串中能延伸的距离 40  41 至于加入#后多出了的回文串，可以发现不管是lc[]还是height[]长度都是延伸到#位置的也就是相减后/2就是原串的个数 42 还有加进了#最后答案要减去1;  43   44 */ 45 #include
     
       46 #include
      
        47 #include
       
         48 #include
        
          49 #include
         
           50 #include
          
            51 #include
           
             52 using namespace std; 53 typedef long long LL; 54 const int N=200000+10; 55 char s[N],s1[N]; 56 struct SuffixArray{ 57 int a1[N],a2[N],c[N],SA[N],sa[N],*rank,*x,*y; 58 int n,height[N],m; 59 void sort(){ 60 for (int i=0;i
            
             =0;i--) SA[ --c[x[sa[i]]] ] = sa[i]; 64 } 65 void build_sa(char *s){ 66 n=strlen(s); m=256; 67 x=a1; y=a2; x[n]=y[n]=-1; 68 for (int i=0;i
             
              =k) sa[p++]=SA[i]-k; 74 sort(); 75 p=0; swap(x,y); 76 x[SA[0]]=0; 77 for (int i=1;i
              
               =p){113 int j=0;114 while (i-j>=0 && i+j
               
                =0 && i+d
                
                 =tmp) tmp=lc[t];140 else {141 tmp=min(tmp,H.height[i]);//从上一个传递到当前； 142 if (lc[t]>tmp) tmp=lc[t];//如果该后缀本身的回文个数更多久更新； 143 }144 }145 printf("%d\n",ret-1);146 }147 int main(){148 int T,cas=0;149 scanf("%d",&T);150 while (T--){151 scanf("%s",s1);152 init(s1);153 H.build_sa(s);154 printf("Case #%d: ",++cas);155 solve();156 }157 return 0;158 }159 /*160 6 161 abba162 baab163 aabaa164 aaaa165 abab166 abcd167 168 169 */

hdu 3518

1 /*  2 题意：统计一个字符串里不错至少2次且不覆盖的子串的个数  3   4 后缀数组求出height后，枚举子串的长度L，利用L对height分组  5 对于同一组里的后缀，如果在组里最小后缀和最大后缀的差大于L就说明至少有俩个长度为L串  6 且不覆盖的出现，所以ans++;  7   8 为什么这样不会重复统计，假设长度为L的字串s1是满足要求的串   9 让我们看一下长度为L的子串s1是如何被统计进去的， 10 首先我们知道所有前缀是s1的后缀在SA[]数组里将连续出现，而且相邻的height[]>=L; 11 也就是说只要其中俩个后缀的距离大于等于L就说明他们不重叠； 12 所以串s1只会被统计一次； 13 时间复杂度是o(n^2);  14   15 */ 16 #include
     
       17 #include
      
        18 #include
       
         19 #include
        
          20 #include
         
           21 #include
          
            22 using namespace std; 23 const int N=1000+10; 24 struct SuffixArray{ 25 int a1[N],a2[N],c[N],SA[N],sa[N],*rank,*x,*y; 26 int n,height[N],m; 27 void sort(){ 28 for (int i=0;i
           
            =0;i--) SA[ --c[x[sa[i]]] ] = sa[i]; 32 } 33 void build_sa(char *s){ 34 n=strlen(s); m=256; 35 x=a1;y=a2; x[n]=y[n]=-1; 36 for (int i=0;i
            
             =k) sa[p++]=SA[i]-k; 42 sort(); 43 p=0; swap(x,y); 44 x[SA[0]]=0; 45 for (int i=1;i

g; 68 void solve(){ 69 int ret=0; 70 int n=strlen(s); 71 /* cout<<">.<"<

.<"<

=1;i--){ 77 g.clear(); 78 for (int j=1;j<=n;j++){ 79 if (H.height[j]>=i){ 80 g.push_back(H.SA[j-1]); 81 }else { 82 g.push_back(H.SA[j-1]); 83 sort(g.begin(),g.end()); 84 int sz=g.size(); 85 if (sz>1 && g[sz-1]-g[0]>=i) ret++; 86 g.clear(); 87 } 88 } 89 90 } 91 printf("%d\n",ret); 92 } 93 int main(){ 94 while (~scanf("%s",&s)){ 95 if (s[0]=='#') break; 96 H.build_sa(s); 97 solve(); 98 } 99 return 0;100 }101 /*102 aaaa103 ababcabb104 aaaaaa105 #106 107 */

hdu 4416

1 /*  2 题意：求出现在s串中，但不出现在其他n个串中的字串个数；  3   4 类似统计求一个串中不同的子串个数；  5    6 我的做法是，先链接这些串，定义起点在s中的后缀叫目标后缀；  7 求从前往后，从后往前扫两边，求出每一个目标后缀在SA[]数组中前后  8 最近的非目标后缀和其的LCP，Lx[]中保存的是两个中的较大值；  9 因为有可能多个目标后缀在SA[]数组中是连续的，所以还要减去其中一部分 10 比如 11 2 bab  12 0 babab 13 1 babac 14 3 babd 15 0,1都是目标后缀，2,3都是非目标后缀，那么0,1后缀的非法子串是bab 16 有因为0，1后缀相邻，要减去(height[]-lx[]);  17 所以在统计的时候baba才只被统计一次， 18   19 那么剩下的就是要求的串的个数，  20 */ 21 #include
     
       22 #include
      
        23 #include
       
         24 #include
        
          25 #include
         
           26 #include
          
            27 #include
           
             28 using namespace std; 29 typedef long long LL; 30 const int N=300000+10; 31 struct SuffixArray{ 32 int a1[N],a2[N],c[N],SA[N],sa[N],*rank,*x,*y; 33 int n,height[N],m; 34 void sort(){ 35 for (int i=0;i
            
             =0;i--) SA[ --c[x[sa[i]]] ] = sa[i]; 39 } 40 void build_sa(char *s){ 41 n=strlen(s); m=256; 42 x=a1; y=a2; x[n]=y[n]=-1; 43 for (int i=0;i
             
              =k) sa[p++]=SA[i]-k; 49 sort(); 50 p=0; swap(x,y); 51 x[SA[0]]=0; 52 for (int i=1;i
              
               0;i--){105 if (H.SA[i]
               
                lx[H.SA[i]]) ret-=H.height[i]-lx[H.SA[i]];119 }120 }121 }122 printf("%I64d\n",ret);123 }124 int main(){125 int T,cas=0;scanf("%d",&T);126 while (T--){127 read();128 H.build_sa(s);129 printf("Case %d: ",++cas);130 solve();131 }132 return 0;133 }

转载于:https://www.cnblogs.com/Rlemon/p/3170586.html

你可能感兴趣的文章