73.對稱字符串的最大長度（字符串）。
題目：輸入一個字符串，輸出該字符串中對稱的子字符串的最大長度。
比如輸入字符串“google”，由于該字符串里最長的對稱子字符串是“goog”，因此輸出 4。

?

雖然知道會有簡單的方法，可腦子就是轉(zhuǎn)不動了，只好用最常見的，對所有可能的字符串判斷是否為對稱的。再輸出最大長度 O(N³)

/* 73.對稱字符串的最大長度（字符串）。 題目：輸入一個字符串，輸出該字符串中對稱的子字符串的最大長度。 比如輸入字符串“google”，由于該字符串里最長的對稱子字符串是“goog”，因此輸出 4。 */#include <stdio.h> #include <string.h>bool issymmetry(char * in, int len) //判斷字符串是否對稱 {int i, j;for(i = 0, j = len - 1; i < j ; i++, j--){if(in[i] != in[j]){return false;}}return true; }int maxSubSymLen(char * in, int len) {int nlen;for(nlen = len; nlen >= 1; nlen--) //按長度循環(huán) {if(nlen == 1){return 1;}else{int i;for(i = 0; i <= len - nlen; i++) //首字母位置循環(huán) {if(issymmetry(in + i, nlen)){for(int j = i; j < i + nlen; j++){printf("%c ", in[j]);}return nlen;}}}} }int main() {char a[40] = "asdgjoalsgjeslhfelgjdjglejf";int ans = maxSubSymLen(a, strlen(a));return 0; }

?

網(wǎng)上O（N²）解法是 長度從小向大循環(huán)?

http://blog.163.com/clevertanglei900@126/blog/static/1113522592011912103756405/

如果我們換一種思路，我們從里向外來判斷。也就是我們先判斷子字符串A是不是對稱的。如果A不是對稱的，那么向該子字符串兩端各延長一個字符得到的字符串肯定不是對稱的。如果A對稱，那么我們只需要判斷A兩端延長的一個字符是不是相等的，如果相等，則延長后的字符串是對稱的。因此在知道A是否對稱之后，只需要O（1）的時間就能知道aAa是不是對稱的。

?

/* 取得所有對稱子串的最大長度 時間復雜度： O(n^2) */int GetLongestSymmetricalLength(char* pString) {if(pString == NULL)return 0;int symmeticalLength = 1;char* pChar = pString;while(*pChar != '\0'){// Substrings with odd lengthchar* left = pChar - 1;char* right = pChar + 1;while(left >= pString && *right != '\0' && *left == *right){left--;right++;}int newLength = right - left - 1; //退出while循環(huán)時，*left != *rightif(newLength > symmeticalLength)symmeticalLength = newLength; // Substrings with even lengthleft = pChar;right = pChar + 1;while(left >= pString && *right != '\0' && *left == *right){left--;right++;}newLength = right - left - 1; //退出while循環(huán)時，*left != *rightif(newLength > symmeticalLength)symmeticalLength = newLength;pChar++;}return symmeticalLength; }

?

?

居然還有O（N）的算法！！

http://blog.csdn.net/hackbuteer1/article/details/6686263

經(jīng)常有一些題目圍繞回文子串進行討論，比如 HDOJ_3068_最長回文，求最長回文子串的長度。樸素算法是依次以每一個字符為中心向兩側(cè)進行擴展，顯然這個復雜度是O(N^2)的，關于字符串的題目常用的算法有KMP、后綴數(shù)組、AC自動機，這道題目利用擴展KMP可以解答，其時間復雜度也很快O(N*logN)。但是，今天筆者介紹一個專門針對回文子串的算法，其時間復雜度為O(n)，這就是manacher算法。
大家都知道，求回文串時需要判斷其奇偶性，也就是求aba和abba的算法略有差距。然而，這個算法做了一個簡單的處理，很巧妙地把奇數(shù)長度回文串與偶數(shù)長度回文串統(tǒng)一考慮，也就是在每個相鄰的字符之間插入一個分隔符，串的首尾也要加，當然這個分隔符不能再原串中出現(xiàn)，一般可以用‘#’或者‘$’等字符。例如：
原串：abaab
新串：#a#b#a#a#b#
這樣一來，原來的奇數(shù)長度回文串還是奇數(shù)長度，偶數(shù)長度的也變成以‘#’為中心的奇數(shù)回文串了。
接下來就是算法的中心思想，用一個輔助數(shù)組P記錄以每個字符為中心的最長回文半徑，也就是P[i]記錄以Str[i]字符為中心的最長回文串半徑。P[i]最小為1，此時回文串為Str[i]本身。
我們可以對上述例子寫出其P數(shù)組，如下
新串： # 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。得證。
依次從前往后求得P數(shù)組就可以了，這里用到了DP(動態(tài)規(guī)劃)的思想，也就是求P[i]的時候，前面的P[]值已經(jīng)得到了，我們利用回文串的特殊性質(zhì)可以進行一個大大的優(yōu)化。

#include <stdio.h>#define M 110010char b[M],a[M<<1]; int p[M<<1];int Min(int a,int b) {return a<b?a:b; }int main(void) {int i,n,id,MaxL,MaxId;while(scanf("%s",&b[1])!=EOF){MaxL=MaxId=0;for(i=1;b[i]!='\0';i++){a[(i<<1)]=b[i];a[(i<<1)+1]='#';}a[0]='?';a[1]='#';n=(i<<1)+2;a[n]=0;MaxId=MaxL=0;for(i=1;i<n;i++){if(MaxId>i){p[i]=Min(p[2*id-i],MaxId-i);}else{p[i]=1;}while(a[i+p[i]]==a[i-p[i]]){p[i]++;}if(p[i]+i>MaxId){MaxId=p[i]+i;id=i;}if(p[i]>MaxL){MaxL=p[i];}}printf("%d\n",MaxL-1);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/dplearning/p/3899225.html

總結

以上是生活随笔為你收集整理的【编程题目】对称子字符串的最大长度 ★的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。