回文串"/>
实训四#4.21回文串
问题描述
“回文串”是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串。给你一个字符串,问最少在字符串尾添加多少字符,可以使得字符串变为回文串。
输入格式
有多组测试数据。
每组测试数据第一行是一个正整数N,表示字符串长度,接下来一行是长度为N的字符串,字符串中只有小写字母。
N=0表示输入结束,并且不需要处理。
40%的数列元素个数N 1 ≤ N≤ 100;
30%的数列元素个数N 1 ≤ N≤ 1000;
20%的数列元素个数N 1 ≤ N≤ 10000;
10%的数列元素个数N 1 ≤ N≤ 100000;
输出格式
对于每组测试数据,输出一个非负整数:添加最少的字符数,可以使得字符串变为回文串。
样例输入
3 aba 4 aaac 0
样例输出
0 3
#include <bits/stdc++.h>
using namespace std;bool nrev(string s)
{int n = s.size()/2;int a=0, b=s.size()-1;for (int i=0; i<n; i++) {if (s[a]!=s[b]) return 1;a++, b--;}return 0;
}int main()
{int n, c;while (cin >> n) {if (!n) return 0;string s, u, t; cin >> s;c = -1;do {u=s; t = u.substr(0, c+1); reverse(t.begin(), t.end()); u+=t; c++;} while (nrev(u)); cout << c << endl;}
}
更多推荐
实训四#4.21回文串
发布评论