首页 > 试题广场 >

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

[问答题]

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


题目描述:

求一个字符串的最大回文前缀长度。回文是指正反方向读起来都一样的字符串,比如“abcdcba”就是一个回文。

输入

一个文本文件,至少包含一个字节。每个字节是一个字符。最大长度可能有几十万字节。

输出

最大回文前缀的长度。

样例输入

Sogou

样例输出

1

// 只写两个函数说明思路
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;
}

编辑于 2017-08-17 16:02:48 回复(1)
把字符串切成数组,数组reverse()指向一个新的数组,新旧数组遍历对比。遇到相等时标记数字加1
发表于 2017-11-14 20:02:51 回复(0)

//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;
}
发表于 2017-08-10 23:50:30 回复(0)
java实现:
public static void main(String[] args) {
        System.out.print("请输入一个字符串:");
        Scanner scanner = new Scanner(System.in);
        String string = scanner.nextLine();
        int count = huiwenCount(string);
        if (count == -1) {
            System.out.println("该字符串长度为0不符合要求!");
        } else {
            System.out.println("该字符串最大回文长度为:" + count);
        }
    }

    private static int huiwenCount(String str) {
        // 将j循环的最大回文字符串添加到strList
        ArrayList<String> strList = new ArrayList<>();
        // 将每次j循环后的strList添加到list
        ArrayList<String> list = new ArrayList<>();
        // 最终的最大回文字符串可能不止一个,添加进maxList以便打印显示
        ArrayList<String> maxList = new ArrayList<>();
        if (str == null || str.length() == 0) {
            return -1;
        }
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            String temp = ch + "";
            int lenth = 1;
            for (int j = i + 1; j < str.length(); j++) {
                char cha = str.charAt(j);
                temp += cha;
                if (isHuiwen(temp)) {
                    System.out.println("temp:" + temp);
                    if (temp.length() > lenth) {
                        strList.clear();
                        strList.add(temp);
                        lenth = temp.length();
                    }
                }
            }
            if (strList.size() != 0) {
                list.addAll(strList);
            }
        }
        if (list.size() == 0) {
            return 1;
        } else {
            int max = list.get(0).length();
            String maxString;
            for (int i = 0; i < list.size(); i++) {
                if (list.get(i).length() > max) {
                    max = list.get(i).length();
                    maxString = list.get(i);
                    maxList.clear();
                    maxList.add(maxString);
                } else if (list.get(i).length() == max) {
                    maxList.add(list.get(i));
                }
            }
            System.out.println("最大的回文字符串是:" + maxList.toString());
            return max;
        }
    }

    private static boolean isHuiwen(String str) {
        StringBuilder builder = new StringBuilder(str);
        if (str.equals(builder.reverse().toString())) {
            return true;
        } else {
            return false;
        }
    }
请输入一个字符串:abcbcagfgahag
temp:bcb
temp:cbc
temp:agfga
temp:gfg
temp:gahag
temp:aha
最大的回文字符串是:[agfga, gahag]
该字符串最大回文长度为:5
编辑于 2019-09-07 01:25:48 回复(0)
1.遍历每一个字母 2.回文数为奇数的情况,如果比较当前字母上一个字母与下一个字母是否相等,是则继续比较上上个与下下个并给长度+1,否则不是当前字母无法构成中值为当前字母的回文数 3.偶数的情况,比较当前字母与下一个字母是否相等,否则不是回文数,如果相等,则比较上一个字母与下一个是否相等, 4.取上述两种情况得到的回文数长度最大值,与当前最大值比较,取最大的,完成当前字母遍历
发表于 2018-06-18 14:26:41 回复(1)
<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>
也不知道对不对~  

编辑于 2017-09-23 16:55:54 回复(0)
//借鉴 @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;
}

编辑于 2017-09-08 12:01:54 回复(0)
#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;
}
发表于 2018-09-14 11:24:29 回复(0)

#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
int lenPalindrome(string str, int start, int end){
 int len = 0;
 int i = start;
 int j = end;
 bool isTrue=true;
 while (i < j){
  if (str[i] == str[j]){
   i++;
   j--;
  }
  else{
   isTrue = false;
   break;
  } 
 }
 if (isTrue)
  len = end-start+1;
 return len;
}
int main(){
 string str;
 cin >> str;
 vector<int> loc;
 char firstChar = str[0];
 int length = 1;
 int i;
 for (i = 1; i < (int)str.size(); i++){
  if (str[i] == firstChar)
   loc.push_back(i);
 }
 
 for (i = (int)(loc.size() - 1); i>=0; i--){
  //cout << "与首字母相同的字母位子:" << loc[i] << endl;
  //cout << "length:" << length << endl;
  //cout << "回文长度:" << lenPalindrome(str, 0, loc[i]) << endl;
  length = max(length, lenPalindrome(str,0,loc[i]));
 }
 cout << length << endl;
 system("pause");
 return 0;
}
发表于 2017-09-08 11:34:38 回复(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;
}

发表于 2017-09-07 11:12:47 回复(1)
#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
#include<math.h>
using namespace std;
int main(){
    long long n;
    long long res;
    long long i, j,k;
    int x,y,z;
    char s[1000000];
    while (cin >>s)
    {
        int max = 0;
        n = strlen(s);
        for (i = 0; i < n; i++)
        {
            for (j = 1; s[i - j] == s[i + j] && i - j >= 0 && i + j < n; j++)
                ;
            if (max < 2*j-1)
                max = 2 * j - 1;
        }
        cout <<max<< endl;
    }
    return 0;
}
发表于 2017-09-04 17:00:37 回复(0)

 def maxlen(s):
    max_n = 0
    for i in range(len(s)):
        n = 0
        while (i-n >= 0)and(i+n < len(s)):
            if s[i-n] == s[i+n]:
                n = n+1
            else: break
        if n-1 > max_n: max_n = n-1
    return max_n

if __name__ == "__main__":
    s = "Sogou"
    print(fun(s))
如果字符串的长度为n,时间复杂度为O(n²)
编辑于 2017-08-17 22:02:20 回复(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;
}

发表于 2017-08-17 17:58:10 回复(0)
 
发表于 2017-08-17 15:44:16 回复(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;
	}
};

发表于 2017-08-15 17:33:46 回复(2)
#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;
}

发表于 2017-08-14 21:20:58 回复(0)