经典算法题--求对策字符串的最大长度

题目：输入一个字符串，输出该字符串对称子字符串的最大长度，如输入google，则输出4.

方法一：思路很中规中矩，遍历这个字符串，若有发现相邻的两个字符相等，就循环判断与这两个字符相邻的两个字符是否相等，

   　　  直到不等，记下字符符合条件的字符个数。最大的个数即为所求。

 方法二：在方法一的基础上略有改动，思路还是一样，只不过不是一发现相邻的两个字符相等就开始循环，

           而是根据上次出现对称的字符个数比较对应的两个字符是否相等，

           如果不等，那肯定是不用循环的，我们要求最大的长度吗？哈哈哈...

           如果相等，就向里循环，判断里面的字符是否相等，不等就退出循环，如果都相等的话，说明更长的长度出现了，

           我们开始向外循环，直到不等为止，记下字符的长度。最后得到的值即为所求。

方法一

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;                bool isMore=true;                while(start<i && end>i)                 {                    if(str[start++]!=str[end--])                    {                        isMore=false;                        break;                    }                }                if(!isMore)                {                    continue;                }                 start=i-k;                end=i+k+1;                while(start>-1 && end<strlen)                 {                    if(str[start--]==str[end++])                    {                        maxlen+=2;                    }                }                             }        }        return maxlen ;    }方法二写得有点乱，有待完善，可能存在BUG。

补充：软件开发 , C语言 ,

上一个：C语言学习趣事_数据结构_经典命题_1_背包问题_分析_1
下一个：catalan数证明