P11276 题解

Aventurine_stone · 2024-11-15 10:32:18 · 题解

1. 题目分析

简化一下题意，就是求题目所给的字符串 s 的最长 border 字符串 s1，将 s 除去 s1 的后面字符串部分记为 s2，那么本题答案 t 即为 s 后面接个 s2。

2. 题目做法

想求 s 的最长 border，我们可以快速想到 O(n^2) 的暴力做法，不过这肯定是过不了的。
如果我们在暴力的基础上加入随机化，也就是在判断两个字符串是否相同时随机挑几个字符来判断，这样做赛时能过，不过现在已经被卡掉了。
正解是 KMP 或字符串哈希，我用的是 KMP。可以 O(n) 算出 s 的最长 border。

3. 代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
inline ll read()
{
    ll x=0;
    char c=getchar();
    while(c<'0'||c>'9')
        c=getchar();
    while(c>='0'&&c<='9')
        x=(x<<1)+(x<<3)+c-'0',c=getchar();
    return x;
}
int n;
int ne[N];
char c[N];
int main()
{
    scanf("%s",c+1);
    n=strlen(c+1);
    for(int i=2,j=0;i<=n;i++)
    {
        while(j&&c[i]!=c[j+1])
            j=ne[j];
        if(c[j+1]==c[i])
            j++;
        ne[i]=j;
    }
    printf("%s",c+1);
    for(int i=ne[n]+1;i<=n;i++)
        putchar(c[i]);
    return 0;
}