题目描述:
输入一个字符串,输出该字符串中对称的子字符串的最大长度。比如输入字符串“google”,由于该字符串里最长的对称子字符串是“goog”,因此输出4。
分析:
假设我们需要判断一个子字符串具有aAa的形式(A是aAa的子字符串,可能含有多个字符)。
我们从里向外来判断。也就是我们先判断子字符串A是不是对称的。如果A不是对称的,那么向该子字符串两端各延长一个字符得到的字符串肯定不是对称的。如果A对称,那么我们只需要判断A两端延长的一个字符是不是相等的,如果相等,则延长后的字符串是对称的。因此在知道A是否对称之后,只需要O(1)的时间就能知道aAa是不是对称的。
#include <iostream> using namespace std; int GetLongestSymmetricalLength(char* pString) { if(pString == NULL) return 0; int symmeticalLength = 1; char* pChar = pString; while(*pChar != '\0') { // Substrings with odd length char* pFirst = pChar - 1; char* pLast = pChar + 1; while(pFirst >= pString && *pLast != '\0' && *pFirst == *pLast) { pFirst--; pLast++; } int newLength = pLast - pFirst - 1; if(newLength > symmeticalLength) symmeticalLength = newLength; // Substrings with even length pFirst = pChar; pLast = pChar + 1; while(pFirst >= pString && *pLast != '\0' && *pFirst == *pLast) { pFirst--; pLast++; } newLength = pLast - pFirst - 1; if(newLength > symmeticalLength) symmeticalLength = newLength; //移动指针,遍历判断整个字符串 pChar++; } return symmeticalLength; } int main() { char *a = "gogoogle"; int length = GetLongestSymmetricalLength(a); cout << length << endl; return 0; }
注:从第一个字符开始,就判断是否有最长的对称字符串。移动指针pChar,直到最后。
判断过程分奇、偶两种。