P11276 第一首歌 题解

一道简单的字符串题目。

题目解释

说求一个最短的字符串 \(t\) ，使其满足对于给定的字符串 \(s\) ：

• \(s\) 为 \(t\) 的前缀。

• \(s\) 为 \(t\) 的后缀。

• \(s\) 不为 \(t\) 。

仔细思考一下，则易得 \(t\) 的最短长度的最大值为 \(s\) 的两倍。即当 \(s\) 是一个前缀后缀不相同的字符串时， \(t\) 就是两个拼在一起的 \(s\) 。

考虑非特殊情况，那么也就是删去第二个累加的 \(s\) 中，与其后缀相同的前缀。类似于共用这一部分。

解题思路

观察到要求相同的前缀和后缀，正好在学 KMP 于是这里使用了其前缀数组解决。那么问题便简化了，求出的 \(sum\) 为前缀与后缀的最大重合区间长度，接着输出 \(s\) 除前 \(sum\) 个字符的其他字符即可。

code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
string s1;
int net[maxn];
void build_kmp(string s){
    net[0]=0,net[1]=0;
    int len=0,i=1;
    for(int i=1;i<s.size();i++){
        int j=net[i];
        while(j&&s[i]!=s[j]){
            j=net[j];
        }
        if(s[i]==s[j]) net[i+1]=j+1;
        else           net[i+1]=0;
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>s1;
    build_kmp(s1);
    cout<<s1;         //第一遍无需修改
    for(int i=net[(int)s1.size()];i<(int)s1.size();i++){
        cout<<s1[i];  //输出非重复部分
    }
    return 0;
}