UVA - 11475 Extend to Palindrome —— 字符串哈希 or KMP or 后缀数组

2022-11-02 21:08:46

题目链接：https://vjudge.net/problem/UVA-11475

题意：

给出一个字符串，问在该字符串后面至少添加几个字符，使得其成为回文串，并输出该回文串。

题解：

实际上是求该字符串的“最长回文后缀”，有多种做法，其中用字符串哈希的方法最方便而且速度最快。

字符串哈希：

从字符串的最后一个字符开始，往前进行计算两个哈希值，其中一个按“先高位后低位”的方法计算，另一个按“先低位后高位”的方法计算。如果在某个位置，两个哈希值相等，那么表明该后缀为回文串，求最长的那个即可。

代码如下：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 using namespace std;

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int MOD = 1e9+;

 const int MAXN = 2e5+;

 const LL seed = ;

 char str[MAXN];

 int main()

 {

     while(scanf("%s",str)!=EOF)

     {

         int len = strlen(str);

         int pos = len-;

         LL hash1 = , hash2 = , s = ;

         for(int i = len-; i>=; i--)

         {

             hash1 *= seed, hash1 += str[i];

             hash2 += str[i]*s, s *= seed;

             if(hash1==hash2)

                 pos = i-;

         }

         for(int i = ; i<len; i++) putchar(str[i]);

         for(int i = pos; i>=; i--) putchar(str[i]);

         putchar('\n');

     }

 }

KMP：

1. 根据next数组的next[len]即为字符串前缀与后缀的最长匹配（不包括重叠的情况），可以将字符串的逆串接在其前面，中间用一个分割符隔开，得到新串，求出新串的next数组

1.1 逆串放在前面是因为用逆串的前缀去匹配原串的后缀。

1.2 中间加个分隔符是用于防止逆串匹配到逆串那里去，即防止过界。

2. 假设新串的长度为len，那么next[len]即为可节省的最大长度，因而只需添加len-next[len]个字符即可。

代码如下：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 using namespace std;

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int MOD = 1e9+;

 const int MAXN = 2e5+;

 char x[MAXN];

 int Next[MAXN];

 void get_next(char x[], int m)

 {

     int i, j;

     j = Next[] = -;

     i = ;

     while(i<m)

     {

         while(j!=- && x[i]!=x[j]) j = Next[j];

         Next[++i] = ++j;

     }

 }

 char str[MAXN];

 int main()

 {

     while(scanf("%s",str)!=EOF)

     {

         int len = strlen(str);

         int m = *len+;

         for(int i = ; i<len; i++)

         {

             x[len--i] = str[i];

             x[len++i] = str[i];

         }

         x[len] = '$'; x[m] = ;

         get_next(x, m);

         int pos = len-Next[m]-;

         for(int i = ; i<len; i++) putchar(str[i]);

         for(int i = pos; i>=; i--) putchar(str[i]);

         putchar('\n');

     }

 }

后缀数组：

1.将逆串接在原串的后面，中间用一个分隔符隔开，得到新串。求出新串的后缀数组。

2.枚举原串在新串中的每一个位置i，该位置代表着新串的一个后缀i，设逆串首字符在原串中的位置为j，同样代表着新串的一个后缀j。加入后缀i与后缀j个最长公共前缀lcp满足：i+lcp==len，即表明最长公共前缀已经延伸到原串的串尾，所以该原串的后缀i为回文串。同样，求出最长的那个即可。

代码如下：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 using namespace std;

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int MOD = 1e9+;

 const int MAXN = 2e5+;

 bool cmp(int *r, int a, int b, int l)

 {

     return r[a]==r[b] && r[a+l]==r[b+l];

 }

 int r[MAXN], sa[MAXN], Rank[MAXN], height[MAXN];

 int t1[MAXN], t2[MAXN], c[MAXN];

 void DA(int str[], int sa[], int Rank[], int height[], int n, int m)

 {

     n++;

     int i, j, p, *x = t1, *y = t2;

     for(i = ; i<m; i++) c[i] = ;

     for(i = ; i<n; i++) c[x[i] = str[i]]++;

     for(i = ; i<m; i++) c[i] += c[i-];

     for(i = n-; i>=; i--) sa[--c[x[i]]] = i;

     for(j = ; j<=n; j <<= )

     {

         p = ;

         for(i = n-j; i<n; i++) y[p++] = i;

         for(i = ; i<n; i++) if(sa[i]>=j) y[p++] = sa[i]-j;

         for(i = ; i<m; i++) c[i] = ;

         for(i = ; i<n; i++) c[x[y[i]]]++;

         for(i = ; i<m; i++) c[i] += c[i-];

         for(i = n-; i>=; i--) sa[--c[x[y[i]]]] = y[i];

         swap(x, y);

         p = ; x[sa[]] = ;

         for(i = ; i<n; i++)

             x[sa[i]] = cmp(y, sa[i-], sa[i], j)?p-:p++;

         if(p>=n) break;

         m = p;

     }

     int k = ;

     n--;

     for(i = ; i<=n; i++) Rank[sa[i]] = i;

     for(i = ; i<n; i++)

     {

         if(k) k--;

         j = sa[Rank[i]-];

         while(str[i+k]==str[j+k]) k++;

         height[Rank[i]] = k;

     }

 }

 int dp[MAXN][], mm[MAXN];

 void initRMQ(int n, int b[])

 {

     mm[] = -;

     for(int i = ; i<=n; i++)

         dp[i][] = b[i], mm[i] = ((i&(i-))==)?mm[i-]+:mm[i-];

     for(int j = ; j<=mm[n]; j++)

     for(int i = ; i+(<<j)-<=n; i++)

         dp[i][j] = min(dp[i][j-], dp[i+(<<(j-))][j-]);

 }

 int RMQ(int x, int y)

 {

     if(x>y) swap(x, y);

     x++;

     int k = mm[y-x+];

     return min(dp[x][k], dp[y-(<<k)+][k]);

 }

 char str[MAXN];

 int main()

 {

     while(scanf("%s", str)!=EOF)

     {

         int len = strlen(str);

         int n = *len+;

         for(int i = ; i<len; i++)

         {

             r[i] = str[i];

             r[n--i] = str[i];

         }

         r[len] = '$'; r[n] = ;

         DA(r, sa, Rank, height, n, );

         initRMQ(n, height);

         int pos = len-;

         for(int i = ; i<len; i++)

         {

             int lcp = RMQ(Rank[i], Rank[len+]);

             if(i+lcp==len)

             {

                 pos = i-;

                 break;

             }

         }

         for(int i = ; i<len; i++) putchar(str[i]);

         for(int i = pos; i>=; i--) putchar(str[i]);

         putchar('\n');

     }

 }

码农公寓

相关文章