给出一个长度为 n 的字符串,问需要在字符串后面最小添加多少字符,使得该字符串对称(回文)。
可通过遍历字符串位置,判断 s[ i ] ~ s[ n-1 ] 是否为回文,即寻找一个最长的以字符串最后结尾的子串长度(num) ,然后需要在字符串后面添加的最少字符数为 n - num.
#include <cstdio> #include <iostream> #include <algorithm> #include <cmath> #include <string> #include <cstring> using namespace std; const long long N = 1e10 + 7; const int maxn = 2e5 + 5; const long long INF = 8e18; typedef long long ll; #define for0(i,n) for(int i = 0;i < n;i++) #define for1(i,n) for(int i = 1;i <= n;i++) string s; int n; int jug(int a,int b) { if(a>b)swap(a,b); if(a==b)return 1; while(1) { if(s[a]!=s[b]) return 0; if(abs(a-b)<=1) return 1; a++,b--; } } int main() { cin>>n; cin>>s; string c; int num = 0; //最长回文串的长度 for(int i = 0;i < n;i++) { if(num >= n-i) //退出循环 break; if(s[n-1] == s[i] && jug(n-1,i)==1) //若符合条件,此时 i ~ n-1 为回文串 num = n-i; } int ans = n-num; cout << ans << endl; }
2020.05.16 ICPC Central Europe Regional Contest 2019
原文:https://www.cnblogs.com/emhhbw/p/12912299.html