题解：AT_abc398_f [ABC398F] ABCBA
SunburstFan
·
·
题解
F - ABCBA
题目大意
KMP 板子。
给定一个只包含大写英文字母的字符串 S，要求构造一个以 S 为前缀的最短回文字符串。
解题思路
- 将字符串 S 反转得到 R。
- 构造字符串
C = R + # + S。
- 在 C 上计算 KMP 失配函数，得到末尾位置可匹配的最长前后缀长度 l。
**代码**：
```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;
}
```