P9606 [CERC2019] ABB

MAZHIYUAN · 2023-10-18 12:55:59 · 题解

看题解里都没有用 KMP 的，我就来发一篇吧。

题意

给定一个字符串，求在末尾最少添加多少个字符，使它成为回文串。

思路

因为最近在学 KMP ，所以最先想到。不难发现，将给定字符串翻转，n 减去反串的前缀与原串的后缀相同的最大长度即为所求。

样例2中，原串后缀与反串前缀相同的长度最大的字符串如下：

代码

只需在 KMP 模板题的基础上修改一下

#include<iostream>
using namespace std;
char ch1[400005],ch2[400005];
int n,pre[400005];
int main(){
    scanf("%d %s",&n,ch1+1);
    for(int i=1;i<=n;i++) ch2[i]=ch1[n-i+1];
    for(int i=2,j=0;i<=n;i++){
        j=pre[i-1];
        while(j&&ch2[i]!=ch2[j+1]) j=pre[j];
        if(ch2[i]!=ch2[j+1]) pre[i]=0;
        else pre[i]=j+1;
    }//预处理pre（nxt）数组，与kmp模板相同
    int j=0;
    for(int i=1;i<=n;i++){
        while(j&&ch1[i]!=ch2[j+1]) j=pre[j];
        if(ch1[i]==ch2[j+1]) j++;
    }//记录反串前缀与原串后缀最大匹配长度
    printf("%d",n-j);
    return 0;
}

第一次发题解，表达不好请见谅 orz