2014-05-02 08:29
原题：
Write a function for retrieving the total number of substring palindromes.
For example the input is 'abba' then the possible palindromes= a, b, b, a, bb, abba
So the result is . Updated at //:
After the interview I got know that the O(n^) solution is not enough to go to the next round. It would have been better to know before starting implementing the solution unnecessarily ...
题目：给定一个字符串，统计所有回文子串的个数。O(n^3)的算法是明显的暴力算法，当然要被淘汰了。
解法1：一个简单的优化，是O(n^2)的。从每个位置向两边计算有多少个回文串。这样可以用O(1)空间，O(n^2)时间完成算法。
代码：
// http://www.careercup.com/question?id=5177378863054848
#include <iostream>
#include <string>
#include <vector>
using namespace std; int countPalindrome(const string &s)
{
int n = (int)s.length();
if (n <= ) {
return n;
} int i, j;
int res;
int count; res = ;
for (i = ; i < n; ++i) {
j = ;
count = ;
while (i - j >= && i + j <= n - && s[i - j] == s[i + j]) {
++count;
++j;
}
res += count; j = ;
count = ;
while (i - j >= && i + + j <= n - && s[i - j] == s[i + + j]) {
++count;
++j;
}
res += count;
} return res;
} int main()
{
string s; while(cin >> s) {
cout << countPalindrome(s) << endl;
} return ;
}
解法2：有个很巧妙的回文串判定算法，叫Manacher算法，可以在O(n)时间内找出最长回文字串的长度。这题虽然是统计个数，同样可以用Manacher算法搞定。Manacher算法中有个很重要的概念，叫“最长回文匹配半径”，意思是当前最长回文子串能覆盖到的最靠右的位置。每当我们检查的中心位置处于这个半径之内时，就可以和另一边的对称点进行参照，减少一些重复的扫描。如果处于半径之外，就按照常规的方式向两边扫描了。Manacher算法的思想一两句话很难说清楚，在此提供一个链接吧：Manacher算法处理字符串回文。
代码：
// http://www.careercup.com/question?id=5177378863054848
// Modified Manacher Algorithm
#include <algorithm>
#include <ctime>
#include <iostream>
#include <string>
#include <vector>
using namespace std; class Solution {
public:
long long int countPalindrome(const string &s) {
int n = (int)s.length(); if (n <= ) {
return n;
} preProcess(s);
n = (int)ss.length();
int far;
int far_i; int i; far = ;
c[] = ;
for (i = ; i < n; ++i) {
c[i] = ;
if (far > i) {
c[i] = c[ * far_i - i];
if (far - i < c[i]) {
c[i] = far - i;
}
} while (ss[i - c[i]] == ss[i + c[i]]) {
++c[i];
} if (i + c[i] > far) {
far = i + c[i];
far_i = i;
}
} long long int count = ;
for (i = ; i < n; ++i) {
count += (c[i] + (i & )) / ;
} ss.clear();
c.clear(); return count;
}
private:
string ss;
vector<int> c; void preProcess(const string &s) {
int n;
int i; n = (int)s.length();
ss.clear();
// don't insert '#' here, index may go out of bound.
ss.push_back('$');
for (i = ; i < n; ++i) {
ss.push_back(s[i]);
ss.push_back('#');
}
c.resize(ss.length());
};
}; int main()
{
string s;
Solution sol;
const int big_n = ; s.resize(big_n);
for(int i = ; i < big_n; ++i) {
s[i] = 'a';
} clock_t start, end;
start = clock();
cout << sol.countPalindrome(s) << endl;
end = clock();
cout << "Runtime for test case of size " << big_n << ": "
<< (1.0 * (end - start) / CLOCKS_PER_SEC)
<< " seconds." << endl; while (cin >> s) {
cout << sol.countPalindrome(s) << endl;
} return ;
}