首页 > 代码库 > CareerCup Facebook Total number of substring palindrome
CareerCup Facebook Total number of substring palindrome
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 6.
Updated at 11/11/2013:
For example the input is ‘abba‘ then the possible palindromes= a, b, b, a, bb, abba
So the result is 6.
Updated at 11/11/2013:
After the interview I got know that the O(n^3) solution is not enough to go to the next round. It would have been better to know before starting implementing the solution unnecessarily ...
------------------------------------------------------------------------
Similar to leetcode Longest Palindromic Substring Part II in my blog, the code is like:
#include <iostream> #include <map> #include <algorithm> #include <limits.h> #include <assert.h> #include <string.h> #include <vector> using namespace std; string preprocess(string s) { string res = "^#"; for (int i = 0; i < s.length(); ++i) { res += s[i]; res += '#'; } res += '$'; return res; } int getPalindromeNum(string s) { string str = preprocess(s); int i, j, len = str.length(), C = 0, R = 0, res = 0, ii; vector<int> T(len + 1, 0), P(len + 1, 0); for (i = 1; i < len; ++i) { ii = 2*C - i; P[i] = (R - i) > 0 ? min(P[ii], R-i) : 0; //bug1: P[i] = (R - i) > 0 ? P[i] : 0 while (str[i + P[i] + 1] == str[i - P[i] - 1]) ++P[i]; res += (P[i] + 1) / 2; //bug2: res += P[i]; if (i + P[i] > R) { C = i; R = i + P[i]; } } return res; } int main() { //string s = "abcba"; string s = "aaaaa"; int res = getPalindromeNum(s); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。