馬拉車（Manacher）演算法（具體演算法流程看這個哥們的：https://blog.csdn.net/qq_35065720/article/details/104205920）：
演算法解決：在一個字串中找到最長的回文字串， 實作策略： 以每個位置作為中心，向兩邊擴展，可以確定奇回文，但是偶回文無法這樣做， 解決方法：在字串中間及兩邊插入某種字符，此時可以按照這種方法進行擴展，此時無論奇回文還是偶回文都可以找到， 例如11211，此時添加任意字符在兩邊#1#1#2#1#1#此時均可以進行回文判斷， C++代碼實作：class Solution1 {
public:
char* manacherString(string str) {
char* charArr = new char[str.size() * 2 + 1];
int str_len = str.size();
for (int i = 1; i <= str_len; i++) {
charArr[2 * i] = str[i - 1];
charArr[2 * i + 1] = '#';
}
return charArr;
}
int maxLcpsLength(string str) {
if (str.size() == 0) {
return 0;
}
char* charArr = manacherString(str);
vector<int> pArr(strlen(charArr)); // 回文半徑陣列
int C = -1;
int R = -1;
int max_val = INT_MIN;
for (int i = 0; i != strlen(charArr); i++) {
pArr[i] = R > i ? min(pArr[2 * C - i], R - i) : 1;
// R > i 表示 i在回文右邊界里面，有一個不用驗的區域
// 2*C-i 為 i關于C的對稱點i',兩個瓶頸：1.i'的回文半徑 2. R到我(i)的距離
while (i + pArr[i] < strlen(charArr) && i - pArr[i] > -1) { // 左右兩邊都不越界
if (charArr[i + pArr[i]] == charArr[i - pArr[i]]) { // 在不用驗的區域下再擴一下
pArr[i]++;
}
else {
break;
}
}
if (i + pArr[i] > R) {
R = i + pArr[i]; // 更新右邊界
C = i; // 更新中心位置
}
max_val = max(max_val, pArr[i]); // 全域最大值
}
return max_val - 1;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/65515.html
標籤：其他