[百度]2014百度校园招聘之最长回文串

【题目】

给你一个字符串，找出该字符串中对称的子字符串的最大长度。即求最大回文串。

【思路1】暴力法

即不使用技巧，穷举所有可能。时间复杂度为O(n^3)（时间上最长，不推荐使用），空间复杂度为O(1)。

本思路是从最大长度的字串开始，而不是从最小开始。假如说给定的字符串为len，先遍历长度为len的字串是否为回文串，如果是停止，

如果不是遍历长度为len-1的字串是否是回文串，一次类推。

#include <iostream>
using namespace std;
//是否是回文串
bool IsPalindromeSubNumber(string num){
    int len = num.length();
    for(int i = 0,j=len-1;i < j;i++,j--){
        if(num[i] != num[j]){
            return false;
        }
    }
    return true;
}
void MaxSubPalindromeNumber(string num){
    bool result;
    bool flag = false;
    int len = num.length();
	//遍历字串的长度
    for(int i = len;i > 0;i--){
		//遍历字串的起始位置
        for(int j = 0;j+i <= len;j++){
            result = IsPalindromeSubNumber(num.substr(j,i));
            if(result){
                flag = true;
                cout<<num.substr(j,i)<<endl;
            }
        }
        if(flag){
            break;
        }
    }
}

int main(){
    string num = "djdslkAABCDEAfjdl1234321skjflkdsjfkldsababasdlkfjsdwieowowwpw";
    MaxSubPalindromeNumber(num);
    return 0;
}

【思路2】

假设现在已经遍历到第 i 个字符，要找出以该字符为“中心”的最长对称字符串，我们需要用另两个指针分别向前和向后移动，直到指针到达字符串两端或者两个指针所指的字符不相等。因为对称子字符串有两种情况，所以需要写出两种情况下的代码：

（1） 第 i 个字符是该对称字符串的真正的中心，也就是说该对称字符串以第 i 个字符对称， 比如： “aba”

（2）第 i 个字符串是对称字符串的其中一个中心。比如“abba”。

所以遍历到每个字符都要考虑两种情况，它可能是在奇数个回文串中或者是在偶数个回文串中

#include<string>
#include<iostream>
using namespace std;


string MaxPalindromeNumber(string str){
    int maxLen = 1,start = 0;
    int len = str.length();
    string s = str;
    int left,right;
    for(int i = 0;i < len;i++){
        //奇数字串
        int oddLen = 1;
        left = i-1;
        right = i+1;
        while(left >= 0 && right < len && str[left] == str[right]){
            left--;
            right++;
            oddLen += 2;
        }
        //更新最大长度
        if(oddLen > maxLen){
            maxLen = oddLen;
            //记录当前最大回文串的起始位置
            start = left+1;
        }
        //偶数字串
        left = i;
        right = i+1;
        int evenLen = 0;
        while(left >= 0 && right < len && str[left] == str[right]){
            left--;
            right++;
            evenLen += 2;
        }
        //更新最大长度
        if(evenLen > maxLen){
            maxLen = evenLen;
            //记录当前最大回文串的起始位置
            start = left+1;
        }
    }
    return str.substr(start,maxLen);
}

int main(){
	string str="djdslkAABCDEAfjdl1234321skjflkdsjfkldsababasdlkfjsdwieowowwpw";
	string s=MaxPalindromeNumber(str);
	cout<<s<<endl;
	return 0;
}

【思路三】Manacher算法

算法的基本思路是这样的：把原串每个字符中间用一个串中没出现过的字符分隔#开来(统一奇偶)，同时为了防止越界，在字符串的首部也加入一个特殊符$，但是与分隔符不同。同时字符串的末尾也加入'\0'。算法的核心：用辅助数组p记录以每个字符为核心的最长回文字符串半径。也就是p[i]记录了以str[i]为中心的最长回文字符串半径。p[i]最小为1，此时回文字符串就是字符串本身。
示例：原字符串 'abba’，处理后的新串 ' $#a#b#b#a#\0’，得到对应的辅助数组p=[0,1,1,2,1,2,5,2,2,1]。

详细请看：[算法]Manacher算法之最大回文子串

#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
//数据预处理
char* Init(char* s){
    int len = strlen(s);
    char* str = new char(2*len+4);
    str[0] = '$';
    int index = 1;
    for(int i = 0;i < len;i++){
        str[index++] = '#';
        str[index++] = s[i];
    }
    str[index++] = '#';
    str[index] = '\0';
    return str;
}

char* MaxPalindromeNumber(char* s){
    char *str = Init(s);
    int maxId = 0,center = 1;
    int len = strlen(str);
    int *p = new int[len+1];

    // MaxId为i字符之前最大回文串向右延伸的最大位置
    // id为MaxId对应的最大回文串的中心位置
    for(int i = 1;i < len;i++){
        //初步定i位置字符为中心的半径
        if(maxId > i){
            p[i] = min(maxId - i,p[2*center - i]);
        }
        else{
            p[i] = 1;
        }
        //继续确定i位置字符为中心的半径 这地方用到'$'
        while(str[i-p[i]] == str[i+p[i]]){
            p[i]++;
        }
        //更新MaxId,id
        if(p[i]+i > maxId){
            maxId = p[i] + i;
            center = i;
        }
    }
    // 最大长度
    int maxLen = 0;
    center = 1;
    for(int i = 1;i < len;i++){
        if(str[i] != '#' && p[i] - 1 > maxLen){
            maxLen = p[i] - 1;
            center = i;
        }
    }
    //提取最大回文串
    char* maxStr = new char[maxLen+1];
    int index = 0;
    for(int i = center - maxLen;i <= center + maxLen;i++){
        if(str[i] != '#'){
            maxStr[index++] = str[i];
        }
    }
    maxStr[index] = '\0';
    return maxStr;
}

int main(){
	char* str="skjflkdsjfkldsababasdlkfjsdwieowowwpw";
	cout<<MaxPalindromeNumber(str);
	return 0;
}

相关链接：

[小米]2015小米校招之回文数判断

[网易]字符串回文分割