String-Palindrome Automata

Article Directory

Insert picture description here

principle


Palindromes_Automaton (PAM), also called palindrome tree, is an efficient algorithm for solving palindrome problems and can solve many palindrome problems that Manacher's algorithm cannot solve. It can solve the number of palindrome strings, the number of palindrome strings that are essentially different, the number of palindrome strings within the prefix 0-i, and the number of palindrome strings at the end of a certain subscript.

It is recommended to understand the dictionary tree before learning .

The reason why it is also called a palindrome tree is because it borrows from the dictionary tree and hopes to compress the common part to store all the palindrome substrings. But it is a bit different from the general tree. The palindrome tree has two root nodes, which can be called odd root and even root, respectively corresponding to the case where the palindrome string is odd and even. As shown in the figure below, each time an edge is passed, the value of the edge is added to the left and right of the node, which is used as the basis for building a tree:

Insert picture description here


Then the key is how to build it? There is only one string S now.
We define node 0 as an even-length root, and node 1 as an odd-length root;

  • f a i l [u] fail[u] f a i l [ u ]point u u uThe point the suffix side points to
  • l e n [u] len[u] l e n [ u ]point u u uPalindrome length
  • t r i e [u] [c h] trie[u][ch] t r i e [ u ] [ c h ]The point obtained by adding a character ch before and after the point u
  • s t r [i] str[i] s t r [ i ]Is the first of the string to be constructed i i iBit
  • c n t [i] cnt[i] c n t [ i ]Means to i i iThe number of palindromes at the end
  • l a s t last l a s tPoint to the right end of the longest palindrome substring (must exist, that is, one character)

for l e n [] len[] l e n [ ]It's easier to understand, l e n [0] = 0, l e n [1] = − 1 len[0]=0,len[1]=-1 l e n [ 0 ]=0 ,l e n [ 1 ]=− 1, The even root of 0 is set to 0, and the odd root of 1 is set to -1. In order for the subsequent length -1 to become an odd number, the length of other child nodes is the length of the parent node +2.

The key difficulty is to build f a i l [] fail[] f a i l [ ]Pointer, if you have known AC automata , you will understand better. Similar to AC automata, it returns to the current after mismatch i i iThe longest palindrome at the end is essentially different from the longest palindrome suffix.
 f a i l fail f a i lThe pointer points to the longest palindrome suffix of the node, so when a new character is added, it is necessary to recurse continuously from the current node f a i l fail f a i lPointer, until both sides of the palindrome represented by a certain node can be extended by a character to be added while (str[idx] != str[idx - len[u] - 1])u = fail[u];. Then see if this node has a corresponding child node, if there is, go straight down, if not, create a new node (same as the dictionary tree).

Pay attention to the odd roots and even roots f a i l fail f a i lPointer, because the length of the palindrome represented by the child node of the odd root is 1 (that is, the character itself), the odd root is equivalent to extending any character to both sides, so the even root f a i l fail f a i lThe pointer points to Chigen.

when s t r [i − l e n [l a s t] − 1] ≠ s t r [i] str[i-len[last]-1]≠str[i] s t r [ i−l e n [ l a s t ]−1 ]​=s t r [ i ]When i − 1 i-1 i−1The longest palindrome string cannot be formed by expanding one character S[i] before and after to form a longer palindrome, then l a s t last l a s tSet to f a i l [l a s t] fail[last] f a i l [ l a s t ], Looking for its longest palindrome suffix, you will find it in the end.

template


struct PAM {
    int size, last, r0, r1;
    int trie[maxn][26], fail[maxn], len[maxn], cnt[maxn];
    PAM() {
        r0 = size++, r1 = size++; last = r1;
        len[r0] = 0, fail[r0] = r1;
        len[r1] = -1, fail[r1] = r1;
    }
    void insert(int ch, int idx) {
        int u = last;
        while (str[idx] != str[idx - len[u] - 1])u = fail[u];
        if (!trie[u][ch]) {
            int cur = ++size, v = fail[u];
            len[cur] = len[u] + 2;
            for (; str[idx] != str[idx - len[v] - 1]; v = fail[v]);
            fail[cur] = trie[v][ch]; trie[u][ch] = cur;
            cnt[cur] = cnt[fail[cur]] + 1;
        }
        last = trie[u][ch];
    }
    void build(char* str) {
        int len = strlen(str);
        for (int i = 0; i < len; i++) 
            insert(str[i] - 'a' + 1, i);
    }
}pam;

example


P5496 [Template] Palindrome Automaton (PAM)

P5496 [Template] Palindrome Automaton (PAM)

Topic background
Template question, no background (actually I can't think of a background).
Title description
Given a string ss. Ensure that each character is a lowercase letter. For each position of s, request the number of palindrome substrings ending in that position.
This string is encrypted, except for the first character, all other characters need to be decrypted by the answer in the previous position.
Specifically, if the answer at the i-th (i≥1) position is k, the ASCII ASCII code of the i+1-th character is c when it is read in, and the actual ASCII code of the i+1-th character is (c−97+ k) mod26+97. All characters are lowercase letters before and after encryption.
Input format
One string s per line represents the encrypted string.
Output format
One line, |s| integers. The i-th integer represents the number of palindrome substrings whose original string ends with the i-th character.
Input and output sample
input #1
debber
output #1
1 1 1 2 1 1
input #2
lwk
output #2
1 1 2
input #3
lxl
output #3
1 1 1
Explanation/Prompt
For 100% data, 1≤∣s ∣≤5×10 5

Find the number of palindromes at the end of each point, that is, print c n t [] cnt[] c n t [ ]

( Interstitial anti-climbing information ) Blogger CSDN address: https://wzlodq.blog.csdn.net/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 500005;
char str[maxn];
struct PAM {
    int size, last, r0, r1;
    int trie[maxn][26], fail[maxn], len[maxn], cnt[maxn];
    PAM() {
        r0 = size++, r1 = size++; last = r1;
        len[r0] = 0, fail[r0] = r1;
        len[r1] = -1, fail[r1] = r1;
    }
    void insert(int ch, int idx) {
        int u = last;
        while (str[idx] != str[idx - len[u] - 1])u = fail[u];
        if (!trie[u][ch]) {
            int cur = ++size, v = fail[u];
            len[cur] = len[u] + 2;
            for (; str[idx] != str[idx - len[v] - 1]; v = fail[v]);
            fail[cur] = trie[v][ch]; trie[u][ch] = cur;
            cnt[cur] = cnt[fail[cur]] + 1;
        }
        last = trie[u][ch];
    }
    void build(char* str) {
        int len = strlen(str);
        for (int i = 0; i < len; i++) {
            insert(str[i] - 'a' + 1, i);
            str[i + 1] = (str[i + 1] - 97 + cnt[last]) % 26 + 97;
            printf("%d ", cnt[last]);
        }
    }
}pam;
int main(){
    scanf("%s", str);
    pam.build(str);
    return 0;
}

SP7586 NUMOFPAL-Number of Palindromes

SP7586 NUMOFPAL-Number of Palindromes

The meaning of the question is to
ask for a string to contain several palindrome string
input and output examples
input #1
malayalam
output #1
15
Description/Prompt
0 <|s| <= 1000

statistics c n t [] cnt[] c n t [ ]Can

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100005;
char str[maxn];
struct PAM {
    int size, last, r0, r1;
    int trie[maxn][26], fail[maxn], len[maxn], cnt[maxn];
    PAM() {
        r0 = size++, r1 = size++; last = r1;
        len[r0] = 0, fail[r0] = r1;
        len[r1] = -1, fail[r1] = r1;
    }
    void insert(int ch, int idx) {
        int u = last;
        while (str[idx] != str[idx - len[u] - 1])u = fail[u];
        if (!trie[u][ch]) {
            int cur = ++size, v = fail[u];
            len[cur] = len[u] + 2;
            for (; str[idx] != str[idx - len[v] - 1]; v = fail[v]);
            fail[cur] = trie[v][ch]; trie[u][ch] = cur;
            cnt[cur] = cnt[fail[cur]] + 1;
        }
        last = trie[u][ch];
    }
    void build(char* str) {
        int len = strlen(str);
        for (int i = 0; i < len; i++) 
            insert(str[i] - 'a' + 1, i);
    }
}pam;
int main(){
    scanf("%s", str);
    pam.build(str);
    int ans = 0;
    for (int i = 1; i <= pam.size; i++)
        ans += pam.cnt[i];
    printf("%d", ans);
    return 0;
}

P3649 [APIO2014] Palindrome string

P3649 [APIO2014] Palindrome string

Title description
Give you a string s composed of lowercase Latin letters. We define the existence of a substring of s as the number of times this substring appears in s multiplied by the length of this substring.
For the string s given to you, find the largest existing value among all palindrome substrings.
Input format
One line, a non-empty string s consisting of lowercase Latin letters (a~z).
Output format
Output an integer that represents the largest existing value in all palindrome substrings.
Input and output sample
input #1
abacaba
output #1
7
input #2
www
output #2
4
Description/Prompt
[Sample explanation 1]
Use s∣ to represent the length of the string s.
A substring of a string s 1 s 2 …s ∣s∣ is a non-empty string s i s i+1 s j , where 1≤i≤j≤∣s∣. Each string is its own substring.
A string is called a palindrome if and only if the string is read from left to right and read from right to left are the same.
In this example, there are 7 palindrome substrings a, b, c, aba, aca, bacab, and abacaba. Their existence values ​​are 4, 2, 1, 6, 3, 5, 74, 2, 1, 6, 3, 5, and 7 respectively.
Therefore, the largest existing value of the palindrome substring is 77.
The first subtask has a total of 8 points and satisfies 1≤∣s∣≤100.
The second subtask has a total of 15 points and satisfies 1≤∣s∣≤1000.
The third subtask has a total of 24 points and satisfies 1≤∣s∣≤10000.
The fourth subtask has a total of 26 points, which satisfies 1≤∣s∣≤100000.
The fifth subtask has a total of 27 points and satisfies 1≤∣s∣≤300000.

For the second example www, the palindrome substring ww is recorded only once, because the palindrome is incrementally added to the palindrome tree, so cnt is increased by one during construction, and the statistics are accumulated from the leaf nodes upwardscnt[fail[i]] += cnt[i]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 300005;
char str[maxn];
struct PAM {
    int size, last, r0, r1;
    int trie[maxn][26], fail[maxn], len[maxn], cnt[maxn];
    PAM() {
        r0 = size++, r1 = size++; last = r1;
        len[r0] = 0, fail[r0] = r1;
        len[r1] = -1, fail[r1] = r1;
    }
    void insert(int ch, int idx) {
        int u = last;
        while (str[idx] != str[idx - len[u] - 1])u = fail[u];
        if (!trie[u][ch]) {
            int cur = ++size, v = fail[u];
            len[cur] = len[u] + 2;
            for (; str[idx] != str[idx - len[v] - 1]; v = fail[v]);
            fail[cur] = trie[v][ch]; trie[u][ch] = cur;
        }
        last = trie[u][ch];
        cnt[last] ++;
    }
    void build(char* str) {
        int len = strlen(str);
        for (int i = 0; i < len; i++) 
            insert(str[i] - 'a' + 1, i);
    }
}pam;
int main(){
    scanf("%s", str);
    pam.build(str);
    ll ans = 0;
    for (int i = pam.size; i >= 0; i--) {
        pam.cnt[pam.fail[i]] += pam.cnt[i];
        ans = max(ans, 1ll * pam.cnt[i] * pam.len[i]);
    }
    printf("%lld", ans);
    return 0;
}
Originality is not easy, please do not reprint ( this is not wealthy, the traffic is worse ) the
blogger homepage: https://wzlodq.blog.csdn.net/
are here, don’t you want to comment?
If the article is helpful to you, remember One key triple connection ❤