## Longest text substring

Palindrome string It's the same string as the original string and the reverse string . such as `aba`,`acca`. The first is an odd length palindrome string , The latter is an even length palindrome string .

Longest text substring It's all the substrings of a string , It is a palindrome string with the longest length .

## Brute Force practice

Enumerate all substrings , Determine whether it is a palindrome string , And then look for the maximum length . Finding all the substrings takes a double loop , Judging whether it is a palindrome or not should be repeated , Overall time complexity \(O(n^3)\).

A little bit better , You can enumerate the centers of symmetry , And then expand to both sides , Until two different characters , Enumerate the next center of symmetry , Look for the maximum length , Time complexity \(O(n^2)\).

You can also use DP solve , Find the longest common subsequence of the original string and the inverted string (LCS), Time complexity \(O(n^2)\).

## Manacher Algorithm

Next is the point ,Manacher Algorithm , stay 1975 The year was made by a man named Manacher People invented . In the O(n) To find the longest palindrome string .

Mentioned earlier , Palindrome strings have odd length and even length , Classification discussion is a little complicated , You can refer to here . To avoid categorical discussion , There's a trick that can be used ： Insert a... At the beginning and end of the string and between every two characters `'#'`. such as `abaacca`, After the conversion is `#a#b#a#a#c#c#a#`. So whether it's odd palindrome `aba` Or I wrote back `acca`, After conversion, they are all odd palindromes (`#a#b#a#` and `#a#c#c#a#`).

``````string init(string s) {
string res;
res += '@';  //  Add a sentry at the beginning to prevent crossing the border
for(int i = 0; i < s.size(); ++i) {
res += '#';
res += s[i];
}
res += '#';
res += '\$';  //  At the end, we also add sentinels to prevent crossing the border
return res;
}
``````

\(Manacher\) The idea of the algorithm comes from the idea of enumerating symmetry centers . The algorithm needs to maintain a \(len\) Array ,\(len[i]\) representative \(i\) The length of the longest palindrome string in the center .

set up \(s\) Is the original string ,\(mx\) Is the maximum value of the right endpoint in the palindrome string calculated before , The central position of this palindrome string is \(id\), That is to say \(mx=id+len[id]\).

Every time you calculate ,id The right and left sides of are symmetrical , So when we calculate the right side, we don't need to expand from the center of symmetry to both sides , It's a single line of code ：`len[i] = min(mx - i, len[2 * id - i]);`, This is also Manacher The most critical line of code in .

As shown in the figure below ,\(id\) Right to \(mx\) Between the string and the string \(id\) The left is symmetrical , So the one on the right \(len[i]\) The maximum length is symmetrical to the left \(len[2×id−i]\), Because the palindrome string on the right cannot exceed \(mx\) ( For the reasons, see 2 Pictures ), therefore `len[i] = min(mx - i, len[2 * id - i]);`. \(id\) The length of palindrome string on the right cannot exceed \(mx−i\) The reason is that , If \(len[2∗id−i]\) Longer , As shown in the yellow part below , So the yellow part on the right is the same as the yellow part on the left , Then the black part should be longer , Produce a contradiction . Understand the above content, basically understand \(Manacher\) The algorithm .

The code implementation is as follows ：

If you don't think the explanation of this code is clear, you can directly look at the following template title or take a look at Liu Yi is a senior student Code for

``````int Manacher(string s) {
memset(len, 0, sizeof(len));
int mx = 0, id = 0;
int ans = 0;
for(int i = 1; i < s.size() - 1; ++i) {
if(mx > i) {
len[i] = min(mx - i, len[2 * id - i]);  //  The most critical line of code mentioned above
} else {
len[i] = 1;  //  If  i  Beyond the right boundary, you have to start from scratch
}
while(s[i - len[i]] == s[i + len[i]]) {  //  The ab initio method , It's the extension from the center to both sides mentioned above
++len[i];
}
//  to update  mx  and  id
if(i + len[i] > mx) {
mx = i + len[i];
id = i;
}
ans = max(ans, len[i]);
}
return ans - 1; // len[i]  Maximum of -1  This is the longest palindrome string length of the original string
}
``````

## The template questions ：HDU 3068 The longest palindrome

Topic link ：HDU 3068 The longest palindrome

``````// Author : RioTian
// Time : 20/11/11
#include <bits/stdc++.h>
#define ms(a, b) memset(a, b, sizeof(a))
using namespace std;
const int maxn = 220000;
int len[maxn];
string init(string s) {
string res;
res += '@';
for (int i = 0; i < s.size(); ++i) {
res += '#';
res += s[i];
}
res += '#';
res += '\$';
return res;
}
int Manacher(string s) {
ms(len, 0);
int mx = 0, id = 0;
int ans = 0;
for (int i = 1; i < s.size() - 1; ++i) {
if (mx > i)
len[i] = min(mx - i, len[2 * id - i]);
else
len[i] = 1;

while (s[i - len[i]] == s[i + len[i]]) ++len[i];

if (i + len[i] > mx) {
mx = i + len[i];
id = i;
}
ans = max(ans, len[i]);
}
return ans - 1;
}

int main() {
// freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
string s;
while (cin >> s) {
string tmp = init(s);
cout << Manacher(tmp) << endl;
}
}
``````

## Reference resources

OI wiki

Liu Yi's explanation of horse drawn cart algorithm

Scroll to Top