\(\text{Manacher}\) Come on!
\(\text{Manacher}\) There isn't much prior knowledge than\(\text{KMP}\) Much simpler.
pretreatment
\(\text{Manacher}\) Algorithms are used to solve problems related to echo strings, starting with a few basic concepts: echo centers, echo radii, which can be guessed by looking at the literal meaning of the word.
There is another important issue: for palindromes, there is a difference between odd length or even length, i.e.lit. odd-echo text stringcap (a poem)palindromeObviously, the two types of echo strings need to be processed separately. Obviously the two types of echo strings need to be processed separately, because the center of the echo of an odd echo string is one character, but the center of the echo of an even echo string is between two adjacent characters, so let's see if we can handle it consistently.
It is not difficult to think that since the center of an even echo string is between two adjacent characters, we might as well insert a dummy character between each of the two adjacent characters, such as\(\texttt{\#}\)。
For example, for even-return strings\(\texttt{abba}\)We'll make him into a\(\texttt{\#a\#b\#b\#a\#}\), so that this even-return string becomes an odd-return string, and its return center becomes\(\texttt{\#}\) Now all the echo strings are odd-echo strings! Now that all the echo strings are odd echo strings, we can process them consistently next.
(As to why there is one at the beginning and one at the end, more on that later.)
\(\bf{Manacher}\) arithmetic
\(\text{Manacher}\) algorithm that can be used in the\(O(n)\) The complexity of processing out of theMaximum echo radius with each character (or between two characters) as the center of the echo \(rad[]\)。
Let's start by explaining the definition of the echo radius: if the echo center of this echo string is\(o\)and the right endpoint is\(r\)Then this string of palindromesradius of a palindrome \(rad=r-o+1\), which means that the radius of the echo counts the center of the echo.
So let's get started! Thinking about the plain approach first, it's clear that we can enumerate the center of the palindrome, and then keep expanding to both sides simultaneously, expanding to find the farthest left and right endpoints at different times, in an algorithm calledcenter expansion algorithmTime Complexity\(O(n^2)\), the code won't be released, it's very well typed.
Again noting that we can build on thisradius of a two-minute returnand then hashes the substring with\(O(1)\) comparison, the time complexity is reduced to\(O(n\log n)\)。
Meeting our\(\text{KMP}\) How the algorithm optimizes time complexity: reusing known information, I'm in the\(\text{KMP}\) mentioned in the article, this idea is calledincremental approachAt the same time, this is the embodiment of the dp idea.
So what information do we consider to be reusable? Well, it's obviously a palindrome! And what is the nature of a palindrome?asymmetricalAh! So it turns out that if we've already expanded to this character before, it must be preceded by theContent symmetrical to the current character, then that character will obviously also have the echo radius of the preceding character that is symmetrical to it.
For example, the string\(s=\texttt{babcbab}\)When we enumerate to\(s[6]\) When (the penultimate character), it is clear that this place has been\(s[4]\)(Middle\(\texttt{c}\)) Expanded. By the midpoint formula, the character symmetrical to it is\(s[2\times 4-6]=s[2]\), obviously we've dealt with this earlier\(rad[2]\) Oh, yeah.\(rad[2]=2\)So.\(rad[6]\) would be at least\(2\) up, and of course the radius from the echo to the\(3\) Begin to continue to expand.
But noting that we have only symmetrized to the point calculated earlier.is not guaranteed to be completely symmetric to the entire substring of the palindromeFor example, for the string\(t=\texttt{babcbad}\)The following is an example of how to enumerate to the\(s[6]\) (the penultimate character), although it is possible to pass the previous\(s[4]\)(Middle\(\texttt{c}\)) symmetrical to\(s[2\times 4-6]=s[2]\)But\(rad[6]\) but can't get to\(rad[2]\)(see for yourself if it is), why?
Because while the center of the refrain can be symmetrically over, the\(s[4]\) (used form a nominal expression)\(rad\) Not long enough.\(s[7]\) can't be symmetrically past, so this doesn't guarantee that the entire echo string will be symmetrically past, and the solution is theIt can only be utilized with \(s[4]\) Information up to the right endpoint of the longest echo string for the center of the messageIn other words.\(rad[6]\) cannot be directly equal to\(rad[2]\)I've got to keep up with you.in order to \(s[4]\) The longest extensible length up to the right endpoint of the longest echo string that is the center of the echo is taken as \(\min\)。
Formally, let the echo center of the echo string we are utilizing be\(o\)and the right endpoint is\(r\)Now enumerate to\(s[i]\) both (... and...)\(s[i]<r\)(i.e. can be utilized is previous information) then:
Then just continue with the center extension.
account for：\(\min\) A parameter to the symmetric past character is the character corresponding to the\(rad\), obtained by the midpoint formula; and\(\min\) The second parameter ofexist \(r\) and up to the maximum length that can be extended, which I believe you should understand after the previous explanation.
Then, while enumerating, keep updating the\(o\) cap (a poem)\(r\) Ready to go.
Take a look at the code:
int n;
char a[N],s[N<<1];
void manacher(){
// Special handling
int cur=0;
s[0]='@';
s[++cur]='#';
for(int i=1;i<=n;i++) s[++cur]=a[i],s[++cur]='#';
s[++cur]='!' ;
n=cur-1;
// Next it's time for consistent processing
for(int i=1,o=0,r=0;i<=n;i++){
rad[i]=(i>r?1:min(rad[(o<<1)-i],r-i+1)); // use the previous information
while(s[i-rad[i]]==s[i+rad[i]]) rad[i]++; // center expansion
if(i+rad[i]-1>r) o=i,r=i+rad[i]-1; // update o and r
}
}
a It's the original string.s is the processed string.
Let's start with how to calculate the actual original string to\(i\) is the length of the longest echo string in the center of the echo, which is actually the length of the\(rad[i]-1\)(Characters added because of special handling)\(\texttt{\#}\)), categorize and discuss it yourself\(s[i]\) Yes or no.\(\texttt{\#}\)It will be easy to roll out this equation.
We can then answer the question above as to why the head and tail should each have a\(\texttt{\#}\)? As an example, for the string\(\texttt{bac}\)which should actually be converted to\(\texttt{\#b\#a\#c\#}\)Then after enumerating to\(\texttt{a}\) When this is the case, the echo string you actually get is\(\texttt{\#a\#}\)So we should do the same for the first and last characters, so we add one before and one after.\(\texttt{\#}\); or if you think about it, if the two sides don't don't add up, then the\(rad=1\), so the length of the longest echo string with it as the center of the echo is\(rad-1=1-1=0\) up, so fix it that way.
Then why do you have to add\(\texttt{@}\) cap (a poem)\(\texttt{!}\) What? It's to prevent crossing the line, or to make expanding the whole string stop at the left and right endpoints, let's say when the whole string is symmetrical, if you enumerate the center of its palindrome, then if you don't add two different characters to either side, it will keep expanding, and that's crossing the line.
There's not much else to say. Watch out when\(i>r\) When the time comes, it will come directly from the\(1\) Just start the Violence Center extension.
\(\bf{Manacher}\) complexity theory
First of all, the answer must be.\(O(n)\) The.Based on the fact that the string algorithm is all linear。
\(\text{KMP}\) You know how to analyze it, so think for yourself, the answer is below.
\(\color{white}\text{Again the only thing to analyze is the while, everything else is clearly O(n). \)
\(\color{white}\text{Each character is violently expanded from behind it at most once, so it will only be done O(n) times while.}\)
\(\color{white}\text{In summary, actual complexity O(n).} \)
Tired.! But so!