经典算法题--求对策字符串的最大长度(第二版)
方法一：思路很中规中矩，遍历这个字符串，若有发现相邻的两个字符相等，就循环判断与这两个字符相邻的两个字符是否相等，
直到不等，记下字符符合条件的字符个数。最大的个数即为所求。(此方法适合如google这样的字符串)
方法二：思路和方法一时一样的，适合ggoggle这样的字符串。
方法三：满足题意，适合任何类型的字符串。就是时间复杂度为O(n^2)。
int counterplan1(conststring 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(conststring str)
{
int strlen=str.length();
int maxlen=0;
for(int i=1;i<strlen-1;i++)
{
if(str[i-1]==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)
{
maxlen=end-start;
}
}
}
return maxlen ;
}
int counterplan3(conststring str)
{
int strlen=str.length();
int maxlen=0;
int start=0,end=strlen-1;
while(start<end)
{
if(str[start]!=str[end])
{
if(start==end)
{
++start;
end=strlen-1;
}else{
--end;
continue;
}
}
int i=start,j=end;
bool isOK=false;
while(i<j &&!isOK){
while(str[++i]==str[--j])
{
if(i<j-2)
{
continue;
}
if(end-start+1>maxlen)
{
maxlen=end-start+1;
}
isOK=true;
break;
}
i=++start;j=end;
}
if(strlen-start<=maxlen-1)
{
break;
}
}
return maxlen ;
}
