Ural 1297 Palindrome（后缀数组+最长回文子串）-白红宇

Ural 1297 Palindrome（后缀数组+最长回文子串）

阅读量：5155 次

发布时间：2019-06-13

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

题意：

求最长回文子串。

思路：

先将整个字符串反过来写在原字符串后面，中间需要用特殊字符隔开，那么只需要某两个后缀的最长公共前缀。当然，这两个后缀不是让你随便选的，我们需要先确定回文串的中心（那么这儿就需要注意一下奇偶数的情况了，具体可以看一下代码），确定了中心之后，在后面的逆串中，我们也要找到这个中心点的位置，要求的是这两个后缀的公共前缀。

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 #include
            
              9 #include
              10 #include
              
                11 using namespace std; 12 typedef long long ll; 13 typedef pair
               
                 pll; 14 const int INF = 0x3f3f3f3f; 15 const int maxn=2000+5; 16 17 int n; 18 char s[maxn]; 19 int sa[maxn],t[maxn],t2[maxn],c[maxn]; 20 int Rank[maxn],height[maxn]; 21 int d[maxn][30]; 22 23 void build_sa(int m) 24 { 25 int *x=t,*y=t2; 26 //基数排序 27 for(int i=0;i
                
                 =0;i--) sa[--c[x[i]]]=i; 31 for(int k=1;k<=n;k<<=1) 32 { 33 int p=0; 34 //直接利用sa数组排序第二关键字 35 for(int i=n-k;i
                 
                  =k) y[p++]=sa[i]-k; 37 //基数排序第一关键字 38 for(int i=0;i
                  
                   =0;i--) sa[--c[x[y[i]]]]=y[i]; 42 //根据sa和y计算新的x数组 43 swap(x,y); 44 p=1; 45 x[sa[0]]=0; 46 for(int i=1;i
                   
                    =n) 49 break; 50 m=p; //下次基数排序的最大值 51 } 52 } 53 54 void getHeight(int n) 55 { 56 int i,j,k=0; 57 for(i=1;i<=n;i++) Rank[sa[i]]=i; 58 for(i=0;i
                    
                     y) swap(x,y); 86 x--; y--; 87 if(y<0) return 0; 88 return query(x+1,y); 89 } 90 91 int main() 92 { 93 //freopen("in.txt","r",stdin); 94 while(~scanf("%s",s)) 95 { 96 int len = strlen(s); 97 s[len]='1'; 98 for(int i=0;i
                     
                      ans)109 {110 ans=2*tmp-1;111 start=i-tmp+1;112 }113 tmp=LCP(i,n-i-1); //长度为偶数的情况114 if(2*tmp>ans)115 {116 ans=2*tmp;117 start=i-tmp;118 }119 }120 for(int i=start;i

转载于:https://www.cnblogs.com/zyb993963526/p/7580290.html

你可能感兴趣的文章