一个字符串的最大回文前缀长度

// 只写两个函数说明思路
bool is_palindrome(const string& s, int left, int right)
{
	while (left++ < right--)
	{
		if (s[left] != s[right])
			return false;
	}
	return true;
}

int find_max_prefix_palindrome(const string& s)
{
	// 根据前缀的特点，找到所有与第一个字符相等的元素下标，放到vec中
	vector<int> vec;
	for (int i = 1; i < s.length(); ++i)
	{
		if (s[i] == s[0])
			vec.push_back(i);
	}
	// 从后开始，找到回文就返回
	for (int i = vec.size() - 1; i >= 0; i--) 
	{
		if (is_palindrome(s, 0, vec[i]))
			return (vec[i] + 1);
	}
	return 1;
}

//manacher算法

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<char> manacherString(const string &str){
    string::size_type len = str.size();
    vector<char> res(2 * len + 1);
    string::size_type index = 0;
    for (string::size_type i = 0; i < res.size(); i++){
        res[i] = (i & 1) == 0 ? '#' : str[index++];
    }
}

int maxLcpsLength(const string &str){
    if (str.length() == 0)
        return -1;
    vector<char> charArr = manacherString(str);
    vector<int> pArr(charArr.size());

    int index = -1;
    int pR = -1;
    int max = INT_MIN;
    for (int i = 0; i != charArr.size(); i++){
        pArr[i] = pR > i ? min(pArr[2 * index - i], pR - i) : 1;
        while (i + pArr[i]<charArr.size() && i - pArr[i]>-1){
            if (charArr[i + pArr[i]] == charArr[i - pArr[i]])
                pArr[i]++;
            else
                break;
        }
        if (i + pArr[i] > pR){
            pR = i + pArr[i];
            index = i;
        }
        max = max > pArr[i] ? max : pArr[i];
    }
    return max - 1;
}

int main()
{
    string str;
    while (cin >> str){
        cout << maxLcpsLength(str) << endl;
    }
    return 0;
}

<script type="text/javascript">
            function huiwen(str){
                var arr = [];
                var arr2 = [];
                for (var i = 1; i < str.length/2 + 1; i++){
                    var reg1 = new RegExp(".{" + i + "}","g")
                    for(var j = 1; j < str.length/2 + 1; j++){
                        var str1 = str.substring(j,str.length);
                        if(reg1.test(str1)){
                            arr = arr.concat(str1.match(reg1));
                        }
                    }                                   
                }
                for(var j = 0; j < arr.length; j++){
                    var str1 = Array.of(arr[j]).join(",");
                    var arr1 = str1.split("");
                    arr1.reverse();
                    str1 = arr1.join("");
                    arr1 = str1.substring(0);
                    var reg2 = new RegExp(arr[j] + ".{0,1}" + arr1,"g");
                    if(str.match(reg2)){
                        arr2 = arr2.concat(str.match(reg2));
                    }
                }
                for(var i = 0; i<arr2.length; i++){
                    for(var j = arr2.length - 1; j > 0; j--){
                        if(arr2[j].length < arr2[j-1].length){
                            console.log(arr2[j].length);
                            var item = arr2[j];
                            arr2[j] = arr2[j-1];
                            arr2[j-1] = item;
                        }
                    }
                }
                return arr2[arr2.length-1];
            }
            </script>
也不知道对不对~  

//借鉴 @guansdu  的思路，根据前缀的特点，找到所有与第一个字符相等的元素下标，放到vec中。从后开始，找到回文就返回
//不过我写顺手了，就从前向后找了。效率低一些，需要的自己改一下。 #include <iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
	//最大几十万字符不过1M内存，内存应该够用的。
	string str;
	cin >> str;

	char firstChar = str[0];
	vector<int> vIndex;

	// 找到所有符合条件的下标，不包括第一个字符本身。
	for (int i = 1; i < str.size(); i++)
	{
		if (firstChar == str[i])
			vIndex.push_back(i);
	}

	if (vIndex.empty())
	{
		cout << 1 << endl;
		system("pause");
		return 1;
	}

	int maxCount = 1;    //注意，这里默认设为1
	for (vector<int>::iterator it = vIndex.begin(); it != vIndex.end(); it++)
	{
		int count = 0;    //这里默认设为0
		int index = *it;
		for (int i = index, j = 0; i >= j; i--, j++)
		{
			if (i == j)    //回文前缀为奇数时，最后 i == j，只加一个字符数。
				count++;
			else if (str[i] == str[j])
				count = count + 2;
			else
			{
				count = 0;  break;
			}
		}
		maxCount = maxCount > count ? maxCount : count;
	}
	cout << maxCount << endl;
	system("pause");
	return maxCount;
}

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

bool is_palindrome(string str, int left, int right){
   while(left<right){
        if(str[left++]!=str[right--]){
            return false;
        }
    }
    return true;
}
int main(){
    string str;
    cin>>str;
    vector<int> vec;
    for(int i=1;i<str.size();i++){
        if(str[i]==str[0]){
            vec.push_back(i);
        }
    }
    for(int j=vec.size()-1;j>=0;j--){
        if(is_palindrome(str, 0, vec[j])){
            cout<<(vec[j]+1)<<endl;
            return 0;
        }
    }
    cout<<1<<endl;
    return 0;
}

	/*不知道自己思路队不对，大家给看看呗。用的递归



	写一个函数，判别一个字符串是不是回文。若不是，就将最后一个字符删除，然后递归判断新的字符串是不是回文，直到字符串长度为1*/



	#include <iostream>



	#include <vector>



	#include <algorithm>



	#include <string>



	using namespace  std;



	



	
	

		string maxHui(string str){
	

	

		if (str.length() == 1){
	

	

		return str;
	

	

		}
	

	

		int j = str.length() - 1;
	

	

		for (int i = 0; i < str.length()/2; i++){
	

	

		if (str[i] == str[j])
	

	

		j--;
	

	

		else{
	

	

		str = str.substr(0, str.length() - 1);
	

	

		maxHui(str);
	

	

		}
	

	

		if (i == j||j==-1)
	

	

		return str;
	

	

		}
	

	

		}
	




	
	

		int main(){
	

	

		string str;
	

	

		cin >> str;
	

	

		str=maxHui(str);
	

	

		cout<< str.length()<<endl;
	




	return 0;



	}

#include <vector>
#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

int main(int argc, char *argv[])
{
    string input, target;
    cin >> input;
    target.push_back('^');
    for (auto c : input) {
        target.push_back(c);
        target.push_back('#');
    }
    target.push_back('$');

    int res = 0, maxright = 0, maxindex = 0;
    vector<int> table(target.size(), 0);
    for (int i = 1; i < target.size(); ++i) {
        if (i < maxindex) {
            table[i] = min(table[2*maxindex-i], maxright-i);
        }
        while (target[i-table[i]-1] == target[i+table[i]+1]) ++table[i];
        if (table[i]+i > maxright) {
            maxright = table[i]+i;
            maxindex = i;
        }
        if (i-table[i] == 1) {
            res = max(res, i);
        }
    }
    cout << res << endl;
    return 0;
}

	int maxlen(string str)
	{
		int length = str.size();
		if (length == 0)
			return 0;
		int max = 1, cur = 1;
		for (int i = length - 1; i > 0; i--)
		{
			if (str[i] == str[0])
			{
				int j = 1,k = i-1;
				while (j < k)
				{
					if (str[j++] != str[k--])
						break;
				}
				if (j >= k)
				{
					cur = i + 1;
					if (cur>max)
						max = cur;
				}
			}
		}
		return max;
	}

	void test()
	{
		string str = "sogou";
		cout << maxlen(str) << endl;
	}
};

#include<iostream>
#include<string>
#include<vector>

using namespace std;

bool ishuiwen(string str){
	int n = str.length();
	if(n < 2)
		return true;
	for(int i = 0,j = n-1;i < j;i++,j--)
		if(str[i] != str[j])
			return false;
	return true;
}

int main(){
	string s;
	cin >> s;
	int n = s.length();
	int result = 0;

	for(int len = 1;len <= n;len++)
		if(ishuiwen(s.substr(0,len)))
			result = len;



	cout << result << "\n";

	return 0;
}