编程知识 cdmana.com

Manacher algorithm: a powerful tool to solve the longest palindrome substring

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

版权声明
本文为[RioTian]所创,转载请带上原文链接,感谢

Scroll to Top