抓住2018年的尾巴，我們的學習不能止步，本文將給大家講述的是關于最大對稱字符串的算法，需要的朋友可以參考下其中的內容詳情。
算法一：O(n^3)
判斷字串是否對稱是從外到里， O(n)
?
?
/*
?*判斷起始指針，到結束指針的字符串是否對稱
?*/
int IsSymmetrical(char* pBegin, char* pEnd)
{
??? if(pBegin == NULL || pEnd == NULL || pBegin > pEnd)
??? return 0;
??? while(pBegin ??? {
??? if(*pBegin != *pEnd)
??????? return 0;
??? pBegin++;
??? pEnd--;
??? }
??? return 1;
}
/*
?*查找最大對稱字串長度，時間復雜度是O(n^3)
?*/
int GetLongestSymmetricalLength(char* pString)
{
??? if(pString == NULL)
??? return 0;
??? int symmetricalLength = 1;
??? char* pFirst = pString;
??? int length = strlen(pString);
??? while(pFirst ??? {
??? char* pLast = pFirst + 1;
??? while(pLast ??? {
??????? if(IsSymmetrical(pFirst, pLast))
??????? {
??????? int newLength = pLast - pFirst + 1;
??????? if(newLength > symmetricalLength)
??????????? symmetricalLength = newLength;
??????? }
??????? pLast++;
??? }
??? pFirst++;
??? }
??? return symmetricalLength;
}
int main()
{
??? char* str = "google";
??? int len = GetLongestSymmetricalLength(str);
??? printf("%d", len);
??? return 0;
}
算法2： O(n^2)
?
判斷字串是否對稱是從外到里， O(1)
?
?
int GetLongestSymmetricalLength(char* pString)
{
??? if(pString == NULL)
??? return 0;
??? int symmetricalLength = 1;
??? char* pChar = pString;
??? while(*pChar != '/0')
??? {
??? //奇數長度對稱， 如 aAa
??? char* left = pChar - 1;
??? char* right = pChar + 1;
??? while(left >= pString && *right != '/0' && *left==*right)
??? {
??????? left--;
??????? right++;
??? }
??? int newLength = right - left - 1;?? //退出循環是*left!=*right
??? if(newLength > symmetricalLength)
??????? symmetricalLength = newLength;
??? //偶數長度對稱， 如 aAAa
??? left = pChar;
??? right = pChar + 1;
??? while(left >= pString && *right != '/0' && *left==*right)
??? {
??????? left--;
??????? right++;
??? }
??? newLength = right - left - 1;?? //退出循環是*left!=*right
??? if(newLength > symmetricalLength)
??????? symmetricalLength = newLength;
??? pChar++;
??? }
??? return symmetricalLength;
}
int main()
{
??? char* str = "google";
??? int len = GetLongestSymmetricalLength(str);
??? printf("%d", len);
??? return 0;
}
?
算法3：manacher算法
?原串：abaab
新串：#a#b#a#a#b#
這樣一來，原來的奇數長度回文串還是奇數長度，偶數長度的也變成以‘#'為中心的奇數回文串了。
接下來就是算法的中心思想，用一個輔助數組P記錄以每個字符為中心的最長回文半徑，也就是P[i]記錄以Str[i]字符為中心的最長回文串半徑。P[i]最小為1，此時回文串為Str[i]本身。
我們可以對上述例子寫出其P數組，如下
新串： # a # b # a # a # b #
P[]? :? 1 2 1 4 1 2 5 2 1 2 1
我們可以證明P[i]-1就是以Str[i]為中心的回文串在原串當中的長度。
證明：
1、顯然L=2*P[i]-1即為新串中以Str[i]為中心最長回文串長度。
2、以Str[i]為中心的回文串一定是以#開頭和結尾的，例如“#b#b#”或“#b#a#b#”所以L減去最前或者最后的‘#'字符就是原串中長度的二倍，即原串長度為(L-1)/2，化簡的P[i]-1。得證。
注: 不是很懂， 自己改了
?
?
int GetLongestSymmetricalLength(char* pString)
{
??? int length = strlen(pString);
??? char* pNewString = malloc(2*length+2);
??? int i;
??? for(i=0; i
??? *(pNewString+i*2) = '#';
??? *(pNewString+i*2+1) = *(pString+i);
??? }
??? *(pNewString+2*length) = '#';
??? *(pNewString+2*length+1) = '/0';
??? printf("%s/n", pNewString);
??? int maxLength = 1;
??? char* pChar;
??? for(i=0; i??? {
??? int newLength = 1;
??? pChar = pNewString + i;
??? char* left = pChar-1;
??? char* right = pChar+1;
??? while(left>=pNewString && *right!='/0'&& *left==*right)
??? {
??????? left--;
??????? right++;
??????? newLength++;
??? }
??? if(newLength > maxLength)
??????? maxLength = newLength;
??? }
??? return maxLength-1;
}
int main()
{
??? char* str = "google";
??? int len = GetLongestSymmetricalLength(str);
??? printf("%d", len);
??? return 0;
}
以上就是關于最大對稱字符串的算法，想必都已有了一定的了解，更多相關內容請繼續關注武林技術頻道。
新聞熱點
疑難解答
圖片精選
