题解：AT_abc398_f [ABC398F] ABCBA

F - ABCBA

题目大意

KMP 板子。

给定一个只包含大写英文字母的字符串

S

，要求构造一个以

S

为前缀的最短回文字符串。

解题思路

将字符串 $S$ 反转得到 $R$ 。
构造字符串 C = R + # + S。
在 $C$ 上计算 $KMP$ 失配函数，得到末尾位置可匹配的最长前后缀长度 $l$ 。

l

表示

S

的开头与

R

的结尾重合的最大部分，因此只需将

R

剩下未匹配的前缀部分拼接到

S

后，即为最短回文。

代码：

CPP

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    string s;
    cin>>s;

    string r=s;
    reverse(r.begin(),r.end());

    string c=r+"#"+s;
    int n=c.size();
    vector<int> p(n,0);

    for(int i=1;i<n;i++){
        int j=p[i-1];
        while(j>0&&c[i]!=c[j]){
            j=p[j-1];
        }
        if(c[i]==c[j]){
            j++;            
        }
        p[i]=j;
    }

    int l=p.back();
    string a=r.substr(l);
    
    cout<<s+a;

    return 0;
}

题解：AT_abc398_f [ABC398F] ABCBA

文章操作

F - ABCBA

题目大意

解题思路

相关推荐

评论

题解：AT_abc398_f [ABC398F] ABCBA