CF1326 D2

Prefix-Suffix Palindrome

题目大意:给你一个字符串,你需要找到一个最长的只能由原串的前缀和后缀构成且是回文的字符串。

原题链接

input

5
a
abcdfdcecba
abbaxyzyx
codeforces
acbba

output

a
abcdfdcba
xyzyx
c
abba

解题思路:

首先,要满足只能由前缀和后缀构成且是回文,那我们考虑先从首和尾开始取相同的字符(这样一定满足回文)直到碰到不相同的字符,我们记首开头的为s1,尾结束的为s2。

然后,为了要保证最长,我们在剩下的串中从首或者尾开始取出最长的回文串mids。(注意,一定要从头和尾开始,不然满足不了只要前缀和后缀构成)。

那么,我们的答案就是s1+mids+s2,显然满足题目中的条件。

但是,这题的mids怎么去求呢,也就是说一个串的最长前缀回文串怎么去求。暴力的方法是n^2,但是这题的n是10^6,显然不可行。有没有高效的求法呢,主要有两种,一种是 Manache 算法(占个坑,以后有机会补)。还有一种是kmp算法(也是今天刚学,呜呜呜)。这里来讲一下如何用kmp求最长前缀回文。

没学过kmp的可以看下笔者的这篇笔记。

我们知道,kmp算法中有一个求nex[j]数组的重要步骤。(nex[j]表示从0-j前缀中(不包括j)的前缀和后缀相等的最长长度)。那么,我们只需将mids翻转得到的rev和原来的mids串拼接起来,得到s。这样mids最长的前缀回文串就出现在s的后缀,这个时候如果满足前缀和后缀相等,那么就等价于满足了回文这个条件,也就是说我们只要求nex[slen]就行了。

但是还有个细节要注意下,我们看下如果mids=“uwwuw”,那么s=“uwwuwwuwwu” 对于这样的s,我们所求出来的nex[slen]=7,但实际上满足题意的解应该为4,原因是我们的最长回文前缀原则上应小于mids的长度,但转化为求nex的时候这个限制没了。

所以我们可以在拼接起来的时候中间加上一个“¥”,那么s=“uwwuw¥wuwwu”,这样在求nex的时候,对于¥后面的位,我们只会拿¥后的后缀去与前面匹配,就不会越过界了。

AC代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
#define ll long long
#define debug(x) cout<<#x<<'='<<x<<endl
#define set0(x) memset(x,0,sizeof(x))
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=2e6+10;
int nex[maxn];
int getnex(string s)
{
    int len=s.size();
    for(int  i=0;i<=len;i++) nex[i]=0;
    nex[0]=-1;
    int j=0,k=-1;
    while(j<len)
    {   
        if(k==-1||s[j]==s[k]) 
        {
            k++;
            j++;
            nex[j]=k;
        }
        else k=nex[k];
    }
    
    return nex[len];//nex表示的是不含这位的,所以我们要求nex[len]
}
int main()
{
   int t;
   cin>>t;
   while(t--)
   {
       string s;
       cin>>s;
       int len=s.size();
       int st=0,ed=len-1;
        while(st<ed) if(s[st]==s[ed]) st++,ed--;else break;//求出s1和s2
        string mids=s.substr(st,ed-st+1);
        string rev=mids;reverse(rev.begin(),rev.end());
        string qz,hz;
         qz=mids+"¥"+rev;//避免匹配的前缀后缀越界
         int tt=getnex(qz);
         hz=rev+"¥"+mids;
         int mm=getnex(hz);
         if(tt>=mm)
          mids=mids.substr(0,tt);
          else mids=rev.substr(0,mm);
            for(int i=0;i<st;i++)
            cout<<s[i];
            cout<<mids;
            for(int i=st-1;i>=0;i--)
            cout<<s[i];
            cout<<endl;
        
   }
   return 0;
}