【后缀数组】【poj2774】【 Long Long Message】-白红宇

【后缀数组】【poj2774】【 Long Long Message】

阅读量：6987 次

发布时间：2019-06-27

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

题意：

求两个串的最长连续子串。

我的想法：

枚举第二个串...在第一个串的后缀数组中二分查找.

复杂度NlogN。最坏情况N^2

题解：

（3）height 数组：定义height[i]=suffix(SA[i-1])和suffix(SA[i])的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀。

（4） h[i]=height[rank[i]]，也就是suffix(i)和在它前一名的后缀的最长公共前缀。

（5）LCP(i,j)：对正整数i,j 定义LCP(i,j)=lcp(Suffix(SA[i]),Suffix(SA[j])，其中i,j 均为1 至n 的整数。LCP(i,j)也就是后缀数组中第i 个和第j 个后缀的最长公共前缀的长度。其中，函数lcp(u,v)=max{i|u=v}，也就是从头开始顺次比较u 和v 的对应字符，对应字符持续相等的最大位置，称为这两个字符串的最长公共前缀。

2.2 几个性质

（1）LCP(i,j)=min{height[k]|i+1≤k≤j}，也就是说，计算LCP(i,j)等同于询问一维数组height 中下标在i+1 到j 范围内的所有元素的最小值。

（1）最长公共子串。给定两个字符串A 和B，求最长公共子串。

『解析』先将第二个字符串写在第一个字符串后面，中间用一个没有出现过的字符隔开，再求这个新的字符串的后缀数组。当suffix(sa[i-1]) 和suffix(sa[i])不是同一个字符串中的两个后缀时，max{height[i]}才是满足条件

..代码二段有一种WA了1万次才过

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #define oo 0x13131313using namespace std; /* *suffix array *倍增算法 O(n*logn) *待排序数组长度为n,放在0~n-1中，在最后面补一个0 *build_sa( ,n+1, );//注意是n+1; *getHeight(,n); *例如： *n = 8; *num[] = { 1, 1, 2, 1, 1, 1, 1, 2, $ };注意num最后一位为0，其他大于0 *rank[] = { 4, 6, 8, 1, 2, 3, 5, 7, 0 };rank[0~n-1]为有效值，rank[n]必定为0无效值 *sa[] = { 8, 3, 4, 5, 0, 6, 1, 7, 2 };sa[1~n]为有效值，sa[0]必定为n是无效值 *height[]= { 0, 0, 3, 2, 3, 1, 2, 0, 1 };height[2~n]为有效值 * */const int MAXN=300000+5;char S1[MAXN],S2[MAXN];int sa[MAXN];int t1[MAXN],t2[MAXN],c[MAXN];int rank[MAXN],height[MAXN];void build_sa(int s[],int n ,int m){ int i,j,p,*x=t1,*y=t2; for(int i=0;i
              
               =0;i--) sa[--c[x[i]]]=i; for(j=1;j<=n;j<<=1) { p=0; for(i=n-j;i
               
                =j) y[p++]=sa[i]-j; for(i=0;i
                
                 =0;i--) sa[--c[x[y[i]]]]=y[i]; swap(x,y); p=1;x[sa[0]]=0; for(i=1;i
                 
                  =n) break; m=p; }}int s[MAXN];int len1,len2,ans=0;void getHeight(int s[],int n){ int i,j,k=0; for(i=0;i<=n;i++)rank[sa[i]]=i; for(i=0;i
                  
                   len1&&MIN

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #define oo 0x13131313using namespace std; /* *suffix array *倍增算法 O(n*logn) *待排序数组长度为n,放在0~n-1中，在最后面补一个0 *build_sa( ,n+1, );//注意是n+1; *getHeight(,n); *例如： *n = 8; *num[] = { 1, 1, 2, 1, 1, 1, 1, 2, $ };注意num最后一位为0，其他大于0 *rank[] = { 4, 6, 8, 1, 2, 3, 5, 7, 0 };rank[0~n-1]为有效值，rank[n]必定为0无效值 *sa[] = { 8, 3, 4, 5, 0, 6, 1, 7, 2 };sa[1~n]为有效值，sa[0]必定为n是无效值 *height[]= { 0, 0, 3, 2, 3, 1, 2, 0, 1 };height[2~n]为有效值 * */const int MAXN=300000+5;char S1[MAXN],S2[MAXN];int sa[MAXN];int t1[MAXN],t2[MAXN],c[MAXN];int rank[MAXN],height[MAXN];void build_sa(int s[],int n ,int m){ int i,j,p,*x=t1,*y=t2; for(int i=0;i
              
               =0;i--) sa[--c[x[i]]]=i; for(j=1;j<=n;j<<=1) { p=0; for(i=n-j;i
               
                =j) y[p++]=sa[i]-j; for(i=0;i
                
                 =0;i--) sa[--c[x[y[i]]]]=y[i]; swap(x,y); p=1;x[sa[0]]=0; for(i=1;i
                 
                  =n) break; m=p; }}int s[MAXN];int len1,len2,ans=0;void getHeight(int s[],int n){ int i,j,k=0; for(i=0;i<=n;i++)rank[sa[i]]=i; for(i=0;i

转载于:https://www.cnblogs.com/zy691357966/p/5480325.html

你可能感兴趣的文章