Longest Palindromic Substring
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length ofS is 1000, and there exists one unique longest palindromic substring.
这里给出代码如下:
#define get(i) (i? ((i&1)? '-': str[(i>>1)-1]): '$') string longestPalindrome(string &s) { int i, max_right_center = 0, max_right_length = 0; int max_center = -1, max_length = -1, t, len = s.length(); const char *str = s.c_str(); int *p = new int[len << 3]; for (i = 1; '\0' != get(i); ++i){ p[i] = 1; if (max_right_length > i) { int j = (max_right_center<<1) - i; p[i] = std::min(p[j], max_right_length - i); } while (get((i-p[i])) == get((i+p[i]))) ++p[i]; if (p[i] > max_length){ max_length = p[i]; max_center = i; } t = i + p[i]; if (t > max_right_length){ max_right_length = t; max_right_center = i; } } delete [] p; int start = max_center - max_length + 1; start += (start&0x01); start >>= 1; --start; return s.substr(start, max_length - 1); }
可以看一下线性时间回文串的处理方法,值得一提的是最后的长度是max_length - 1;
寻找起点的过程如下:
首先是在$_a_b_c类似的字符串中找到起点。
当发现起点指向_符号的时候,就向前走一格。也就是start += (start & 0x01)
接着再定位一下每个字符在原始字符中的位置。如a的位置是2 原始位置为0.b位置为4,原始位置为1.
则是start = (start>>1)-1
从而可以得到子串。