Testing Round 19

直接看C题。

不难发现是KMP，主要是复习一下KMP。

根据题目要求，寻找的是最长的公共前后缀，且长度需要大于字符串的一半长度。

最后的输出需要注意：一开始写的是找\(v\)中的maxn，然后截取字符串，但是WA了。

实际上找的是最后一个（因为是从整个串找）。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
std::vector<int> prefix_function(string s)
{
    int n=s.length();
    std::vector<int> pi(n);
    for (int i = 1; i < n; ++i)
    {
        int j=pi[i-1];
        while(j>0 && s[i]!=s[j])
        {
            j=pi[j-1];
        }
        if(s[i]==s[j])
        {
            j++;
        }
        pi[i]=j;
    }
    return pi;
}
std::vector<int> KMP(string find, string main)
{
    int size1=find.size();
    int size2=main.size();
    string cur=find+'#'+main;
    std::vector<int> v;
    std::vector<int> lps=prefix_function(cur);
    for (int i = size1; i <= size1+size2; ++i)
    {
        if(lps[i]==size1)
        {
            v.push_back(i-2*size1);
        }
    }
    return v;
}
void solve()
{
    string t;   cin>>t;
    auto v=prefix_function(t);
    if(v.back()<=t.size()/2)
    {
        cout<<"NO\n";
    }
    else
    {
        cout<<"YES\n";
        string ans=t.substr(0,v.back());
        cout<<ans<<"\n";
    }
}    
int main()
{
    int t=1;
    //cin>>t;
    for(int i=1;i<=t;i++)
    {
        //cout<<"case "<<t<<": ";
        solve();
    }
    return 0;
}