题解：AT_abc398_f [ABC398F] ABCBA

Laisira · 2025-03-23 10:33:11 · 题解

求包含字符串 S 的最小回文串。

显然就是 S 翻转后的后缀和 S 的前缀最长相同串补在 S 后面就行了，求一下 S+' '+S' 的 KMP 就行了。

struct KMP{vector<int>nxt;int n;KMP(){n=0;}KMP(string s){int j=0;n=s.size();nxt.resize(n+1);rep(2,n-1,i){while(j&&s[j+1]!=s[i])j=nxt[j];if(s[j+1]==s[i])j++;nxt[i]=j;}}};
///////////////////////////////////////////////////////////
#define Maxn 1000005 
int main()
{
    string s;
    cin>>s;
    int n = s.size();
    string t = s;
    reverse(t.begin(),t.end());
    string S = ' '+t+" "+s;
    KMP kmp(S);
    int k = kmp.nxt[n*2+1];
    // cout<<k<<" ";
    string ans;
    rep(0,n-k-1,i)ans += s[i];
    reverse(ans.begin(),ans.end());
    cout<<s+ans<<"\n";
    return 0;
}