經(jīng)典算法題--求對策字符串的最大長度
題目：輸入一個字符串，輸出該字符串對稱子字符串的最大長度，如輸入google，則輸出4.
方法一：思路很中規(guī)中矩，遍歷這個字符串，若有發(fā)現(xiàn)相鄰的兩個字符相等，就循環(huán)判斷與這兩個字符相鄰的兩個字符是否相等，
直到不等，記下字符符合條件的字符個數(shù)。最大的個數(shù)即為所求。
方法二：在方法一的基礎(chǔ)上略有改動，思路還是一樣，只不過不是一發(fā)現(xiàn)相鄰的兩個字符相等就開始循環(huán)，
而是根據(jù)上次出現(xiàn)對稱的字符個數(shù)比較對應的兩個字符是否相等，
如果不等，那肯定是不用循環(huán)的，我們要求最大的長度嗎？哈哈哈...
如果相等，就向里循環(huán)，判斷里面的字符是否相等，不等就退出循環(huán)，如果都相等的話，說明更長的長度出現(xiàn)了，
我們開始向外循環(huán)，直到不等為止，記下字符的長度。最后得到的值即為所求。
方法一
int counterplan1(const string str)
{
int strlen=str.length();
int maxlen=0;
for(int i=0;i<strlen-1;i++)
{
if(str[i]==str[i+1])
{
int start=i-1;
int end=i+2;
while(start>=0 && end<strlen)
{
if(str[start]==str[end])
{
--start;++end;
}else
{
break;
}
}
if(maxlen<end-start-1)
{
maxlen=end-start-1;
}
}
}
return maxlen;
}
方法二
int counterplan2(const string str)
{
int strlen=str.length();
int maxlen=0;
for(int i=0;i<strlen-1;i++)
{
if(str[i]==str[i+1])
{
int k=maxlen/2;
if(i+k>=strlen)
{
break;
}
int start=i-k;
int end=i+k+1;
while(start<i && end>i)
{
if(str[start++]!=str[end--])
{
break;
}
}
if(start<i)
{
continue;
}
start=i-k;
end=i+k+1;
while(start>-1 && end<strlen)
{
if(str[start--]==str[end++])
{
maxlen+=2;
}
}
}
}
return maxlen ;
}
作者：陳太漢
浙公網(wǎng)安備 33010602011771號