String ::Manacher algorithm

This is the 14th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021.

Reference links and images: oi-wiki.org/string/mana…

Introduction to the

Manacher algorithm, commonly known as horse-drawn cart, was proposed by Glenn K. Manacher in 1975 to find the length of each palindrome string centered on or between characters.

Since a palindrome string can center on a position between two characters, we insert an unused character at both ends of the string and between every two characters, for example, abababb becomes #a#b#a#b#b#.

At this point, the number of palindromes d[I]d[I]d[I] centered on each character position III is calculated, which is also the longest palindrome string length centered on it in the original string +1. [example]

# a # b # a # b # a # b # b #
1 2 1 4 1 6 1 6 1 4 1 2 3 2 1

  a   b   a   b   a   b   b
  1 0 3 0 5 0 5 0 3 0 1 2 1
Copy the code

algorithm

First extend the string as described above, then simply ask for the d[I]d[I]d[I] array. The naive method starts at each location and keeps expanding until it stops, O(n2)O(n^2)O(n2)

For quick calculation, we need to maintain the right-most of the found substring [l,r][L,r][L,r], the one with the largest RRR.

1. D [I]d[I] D [I] D [I]
2. If iii is outside the current palindrome string, that is, I >ri>ri>r, then use the naive algorithm to gradually expand d[I]d[I]d[I] from 111, Stopped updating (l, r), l = I – d + 1 [I], [I] r = I + d – 1 (l, r), l = I – d + 1 [I], [I] 1 r = I + d (l, r), l = I – [I] d + 1, r = I + d – 1 [I].
3. if
   $i<=r$, obviously,
   $l<=i<=r$, can be found at this point
   $i$in
   $(l,r)$A symmetric position in
   $j=r+l-i$, which is divided into two situations:
   1. If [j] j – d + 1 + 1 > > lj – d [j] lj – d + 1 > l [j], [j] so I + d + 1 + 1 < < ri + d [j] [j] + ri + d < 1 r, iii and JJJ because at this time in (l, r) (l, r) (l, r) within the symmetry, D [I]=d[j]d[I]=d[j]d[I]=d[j]

2. If
$j-d[j]+1<=l$, then
$i+d[j]+1>=r$We can’t know
$i$Is there a longer palindrome string outside (l,r) :In this case, let
$d[i]=r-i$, and then use the naive algorithm to extend. It needs to be updated after the extension is complete
$(l,r)$

Complexity analysis

At each step, either III increases or RRR increases, and these two never decrease and are at most NNN, so the complexity is O(n)O(n)O(n) O(n).

code

char str[M], s[M];
int d[M]; //d[I] The number of palindromes centered on I, which is also the longest palindrome centered on I /2+1 in the original string +1
int manacher(char *str) // Process the string, get the d array, return the length of the longest callback substring
{
    s[0] = The '#';
    for(int i=0; str[i]; ++i)
    {
        s[i*2+1] = str[i];
        s[i*2+2] = The '#';
    }
    for(int i=0, l=0, r=0; s[i]; ++i)
    {
        d[i] = 1;
        if(i<r) d[i] = min(d[l+r-i],r-i+1);
        while(i-d[i]>=0 && s[i+d[i]] && s[i-d[i]]==s[i+d[i]])
            ++d[i];
        if(i+d[i]- 1>r)
        {
            r = i+d[i]- 1;
            l = i-d[i]+1; }}int res = 1;
    for(int i=0; s[i]; ++i)
        res = max(res, d[i]- 1);
    return res;
}
Copy the code

Problem sets

Given a string whose length is not more than 11000000, find the length of the longest callback substring.

/* LittleFall : Hello! * /
#include <bits/stdc++.h>
using namespace std; using ll = long long; inline int read(a);
const int M = 23000016, MOD = 1000000007;

char str[M], s[M];
int d[M]; //d[I] indicates I position
// Also represents the longest palindrome string +1 centered on the I /2+1 position in the original string
int manacher(char *str) // Process the string, get the d array, return the length of the longest callback substring
{
    s[0] = The '#';
    for(int i=0; str[i]; ++i)
    {
        s[i*2+1] = str[i];
        s[i*2+2] = The '#';
    }
    for(int i=0, l=0, r=0; s[i]; ++i)
    {
        d[i] = 1;
        if(i<r) d[i] = min(d[l+r-i],r-i+1);
        while(i-d[i]>=0 && s[i+d[i]] && s[i-d[i]]==s[i+d[i]])
            ++d[i];
        if(i+d[i]- 1>r)
        {
            r = i+d[i]- 1;
            l = i-d[i]+1; }}int res = 1;
    for(int i=0; s[i]; ++i)
        res = max(res, d[i]- 1);
    return res;
}
int main(void)
{
	#ifdef _LITTLEFALL_
	freopen("in.txt"."r",stdin);
    #endif

    scanf("%s",str);
	int res = manacher(str);
    printf("%d\n",res );
    return 0;
}


inline int read(a){
    int x=0,f=1;char ch=getchar(a);while(ch<'0'||ch>'9') {if(ch==The '-')f=- 1; ch=getchar(a); }while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar(a); }return x*f;
}
Copy the code

— This article is also published on my CSDN blog.