题解：P11276 第一首歌

题意

这道题需要我们找到一个最短的字符串，使得给定的字符串既是它的前缀也是它的后缀。

KMP算法

用 pi[i] 表示字符串 s[0:i] 的最长的即是前缀又是后缀的子串的长度，那么 pi[n-1] 就是整个字符串最长的即是前缀又是后缀的字串的长度，也就是我们的答案的长度。

假设 k = pi[n-1] ，意味着整个字符串最长的即是前缀又是后缀的字串的长度为 k ，则 s[0:k] 既是s的前缀也是 s 的后缀，那么我们只需要把 s[0:k] 加上 s.substr(k) 就能得到最小的满足条件的答案

计算pi数组

其中 pi 数组是整个题目的关键所在，我们通过 while 循环不断回到之前的前缀位置，直到匹配或找到最大前缀后缀，具体见代码。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6+10;
int pi[N];

int main()
{
    string s;
    cin >> s;
    int n = s.length();
    for(int i=1,j=0;i<n;i++)
    {
        while(j>0 && s[i]!=s[j]) j = pi[j-1];
        if(s[i] == s[j]) j++;
        pi[i] = j;
    }
    int k = pi[n-1];
    cout << s+s.substr(k);
}