一个字符串的最大回文前缀长度
题目描述:
求一个字符串的最大回文前缀长度。回文是指正反方向读起来都一样的字符串,比如“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; }
//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;
}
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
<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; }