输入字符串中对称的子字符串的最大长度

思路：
(1)将字符串str1="roorle"反序为str2 = "elroor"
(2)求str1和str2的最大公共子串

//求两个字符串的最大子串长度
int findMaxSubstr(const char* str1, const char* str2)
{
	if (str1 == NULL || str2 == NULL)
	{
		return 0;
	}

	int max = 0;
	int len1 = strlen(str1);
	int len2 = strlen(str2);
	int** dp = new int*[len2];
	for (int i=0; i<len2; i++)
	{
		dp[i] = new int[len1];
	}

	for (int i=0; i<len2; i++)
	{
		if (str1[0] == str2[i])
		{
			dp[i][0] = 1;
		}
		else
			dp[i][0] = 0;
	}
	for (int i=0; i<len1; i++)
	{
		if (str1[i] == str2[0])
		{
			dp[0][i] = 1;
		}
		else
			dp[0][i] = 0;
	}
	for (int i=1; i<len2; i++)
	{
		for (int j=1; j<len1; j++)
		{
			if (str2[i] == str1[j])
			{
				dp[i][j] = dp[i-1][j-1] + 1;
			}
			else
			{
				dp[i][j] = 0;
			}

			if (dp[i][j] > max)
			{
				max = dp[i][j];
			}
		}
	}

	return max;
}

int maxSubstrLength(const char* str)
{
	if (str == NULL)
	{
		return 0;
	}

	int len = strlen(str);
	char* str1 = new char[len+1];
	char* pstr1 = str1;
	while(len)
	{
		*pstr1++ = str[len-1];
		len--;
	}

	return findMaxSubstr(str, str1);
}

(1).

最长对称子串可能是偶数个字符，也可能是奇数个字符，分别进行判断。当判断的时候，以单个字符或者两个字符为中心，向左右两侧延伸，判断其左右两侧的字符是否相同,时间复杂度O（n^2）.

int getMaxSubstring(char* pstr)
{
    if(pstr==NULL)
    {
        return -1;
    }
    if(pstr==""||pstr[1]=='\0')
    {
        return 1;
    }
    int maxlen = 1;
    char* pchar = pstr + 1;
    while(*pchar != '\0')
    {
        //子串为奇数个字符         
        char *pleft = pchar - 1;
        char *pright = pchar + 1;
        while(pleft >= pstr && pright <= &pstr[strlen(pstr) - 1] && *pleft == *pright)
        {
            pleft--;
            pright++;
        }
        int templen = pright - pleft - 1;
        if(templen > maxlen)
        {
            maxlen = templen;
        }
        //子串为偶数个字符         
        pleft = pchar - 1;
        pright = pchar;
        while(pleft >= pstr && pright <= &pstr[strlen(pstr) - 1] && *pleft == *pright)
        {
            pleft--;
            pright++;
        }
        templen = pright - pleft - 1;
        if(templen > maxlen)
        {
            maxlen = templen;
        }
        pchar++;
    }
    return maxlen;
}

(2).测试用例：

    NULL

    ""

    a

    google

    121

    aabbaa

    111222aabbaa

    测试结果正确

(3).

编程时可能出现的bug有：

a. 没有对字符串为NULL的情况进行判断

b. 最长对称子串可能是偶数个字符也可能是奇数个字符，编程的时候可能考虑不全面

c. pleft >= pstr 和  pright <= &pstr[strlen(pstr) - 1] 没有添加等号，没有判断边界情况

(4).

上述算法的时间复杂度为O(n^2),也可以对字符串的每一个子串进行判断，遍历字符串的每一个字符，然后从该字符开始依次向后取以该字符开始的每一个子串，判断该子串是否为对称子串，然后取最长的对称子串即可，这种方法时间复杂度高，为O(n^3)。

#include <iostream>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <stdio.h>
#define maxn 110055
using namespace std;
char ma[maxn * 2];
int mp[maxn * 2];
int l;
int  Manacher(char s[], int len)
{
    int res = 0;
    l = 0;
    ma[l++] = '$';
    ma[l++] = '#';
    for(int i = 0; i < len; i++)
    {
        ma[l++] = s[i];
        ma[l++] = '#';
    }
    ma[l] = 0;
    int mx = 0, id = 0;
    for(int i = 0; i < l; i++)
    {
        mp[i] = mx > i ? min(mp[2 * id - i], mx - i) : 1;
        while(ma[i + mp[i]] == ma[i - mp[i]]) {
            mp[i] ++;
        }
        if(i + mp[i] > mx)
        {
            mx = i + mp[i];
            id = i;
        }
    }
}
char s[maxn];
int main()
{
    scanf("%s", s);
    int  len = strlen(s);
    Manacher(s, len);
    int ans = 0;
    for(int i = 0; i < l; i++)
    {
        ans = max(ans, mp[i]);
    }
    printf("%d\n", ans - 1);
    return 0;
}

public static int longestSymmtricalLength(String str) {
		if (str == null || str.length() == 0) {
			return -1;
		}
		int symLen = 1;
		char[] letter = str.toCharArray();
		int strLen = str.length();
		int curIndex = 1;
		while (curIndex > 0 && curIndex < strLen - 1) {
			//奇数情况，两个数之间留一个，然后往两端扩展
			int i = curIndex - 1;
			int j = curIndex + 1;
			while (i >= 0 && j <= (strLen - 1) && letter[i] == letter[j]) {
				i--;//如果两边的数相等，i左边的减一，往做扩展，
				j++;//如果两边的数相等，j往右边扩展，直到不符合条件，
			}
			int newLen = j - i - 1;//对称的新的长度
			if (newLen > symLen) {//如果暂时的新的长度大于老的就替换掉老的，
				symLen = newLen;
			}
			i = curIndex;//偶数情况，，，紧挨着的两个数进行比较，其他情况和上面的奇数一样，
			j = curIndex + 1;
			while (i >= 0 && j <= (strLen - 1) && letter[i] == letter[j]) {
				i--;
				j++;
			}
			newLen = j - i - 1;
			if (newLen > symLen) {
				symLen = newLen;
			}
			curIndex++;
		}
		return symLen;
	}