\(\text{Date: 6.27}\)

\(\text{String Notes:}\)

\(\text{Content: I - Manacher, II - The Minium Notation, III - exkmp, IV - AC Automation}\)

\(\text{I - The Manacher}\)

$\text{Definition: } $

\(\text{To solve the longest palindrome substring of a string.}\)

Different Ways to solve the problem.

I Brute force: pick out every substring then check: \(O(n^3)\)

II Choose every Mid then try to expand from both sides: \(O(n^2)\)

III It's easy to find out how to optimize II: use Multiplication(or binary search) to search the maxium length of each Mid. Use hash to check if two string are the same: \(O(n\log n)\)

IV Here it comes: The Manacher!

Step 1:

The problem is, the palindrome string contains the odd-length ones(eg. abcba) and the even-length ones(eg. pddp). We should use different way to solve the two different circumstances.

Sol. : let aabac \(\to\) ~|a|a|b|a|c, which is to put a | character (like $, # or any other you like). Then we don't have to be stucked in this problem.

Step 2:

let \(p[i]\) be the maxium length (currently known) of the palindrome substring which has the Mid \(i\) .

Then let \(MaxR\) be the position of the character(has been touched) at the most right, and \(mid\) be the axis symmerty of the longest palindrome \(MaxR\)-included string .

Then, go through the string with the variable(pointer) \(i\).

If \(i\in[Mid, MaxR]\), then calculate another pointer \(j\) which is symmertric to \(Mid\): \(j = 2Mid-i\).

Then, use \(p[j]\) to update \(p[i]\). Meanwhile, update \(MaxR\) and \(Mid\).

The answer is \(\large\max\limits_{i=1}^{Len}p[i]\).

Summary: Manacher uses the property of palindrome symmetry to simplify the calculation of the maximum palindrome length with one character as the axis of symmetry. Now, this is not a big simplification, but it's a lot faster when you have a lot of data.

\(\text{Code:}\)

#include 
using namespace std;
const int N = 23000002;

char d[N];//the to-solve string
int p[N], cnt, ans;

inline void File() {
    freopen("in.txt", "r", stdin);
    freopen("Ans.txt", "w", stdout);
}

inline void ReadIn() {
    char c = getchar();
    d[0] = '~', d[cnt = 1] = '|';
    while(c < 'a' || c > 'z') c = getchar();
    while('a' <= c && c <= 'z') d[++cnt] = c, d[++cnt] = '|', c = getchar();
}

signed main() {
    File();
    ReadIn();// current i: t, r: MaxR
    for(int t = 1, r = 0, mid = 0; t <= cnt; t++) {//j = (mid << 1) - t
        if(t <= r) p[t] = min(p[(mid << 1) - t], r - t + 1);
        while(d[t - p[t]] == d[t + p[t]]) p[t]++;
        if(p[t] + t > r) r = p[t] + t - 1, mid = t;// update MaxR & mid;
        if(p[t] > ans) ans = p[t];// update ans
    }
    printf("%d\n", ans - 1);
    return 0;
}

\(\text{II - The Miniuim Notation}\)

Use: To solve the smallest-dictionary-sequence string(sub) in a circular string.

Step 1: Let a circular string be a normal one by copying it and add it by the end of the original sequence.(eg. axid\(\to\)axidaxid)

Step 2: Create two pointers \(i,j\) (intially \(i=j=0\)) and two different string \(\in\) the orginal circular string(eg. \(u[], w[]\))(also copy then as \(i_0,j_0\)), then keep moving the pointers to check if \(a[i]=a[j]\). If true \(\to\) i0++, j0++;, If false\(\to\) check which of the two different characters has the larger dictionary-sequence(eg. Let \(u[i_0]). Then let \(j\leftarrow j_0\). Keep doing this until \(i_0-i+1=j_0-j+1=Len(\text{the original string})\). Then the Minium Notation of the origin circular string is found!

\(\text{III - exkmp}\)

\(\large\to\text{An exkmp Blog}\leftarrow\)
Use: To solve the longest prefix of: each suffix of the string \(a\) and string \(b\). (Moreover, the situation of \(a=b\)).

Step 1: Solve \(nxt[i]\) which means compare \(b\) with itself : \(nxt[i]=LCP(b[1,n],b[i,n])\)

Currently we are solving \(nxt[i]\)(\(nxt[1:i-1]\) are all solved), then Find out the max one of \(p=k+nxt[k]-1\).(\(i=k\) is solved before the current \(i\))

\(\Rightarrow b[0,nxt[k]-1]=b[k,p]_{[1]}\to b[x-k,nxt[k] - 1]=b[x,p]_{[2]}\qquad(\text{[1] contains [2]})\)

Let \(L\) be \(nxt[i-k]\)

\(\Rightarrow b[0,L-1]=b[x-k,x-k+L-1]=b[x,x+L-1]\)

void Zx(char *c)
{
    int len = strlen(c);
    int p = 0, k = 1, l; //我们会在后面先逐位比较出 nxt[1] 的值，这里先设 k 为 1
    //如果 k = 0，p 就会锁定在 |c| 不会被更改，无法达成算法优化的效果啦
    nxt[0] = len; //以 c[0] 开始的后缀就是 c 本身，最长公共前缀自然为 |c|
    while(p + 1 < len && c[p] == c[p + 1]) p++;
    nxt[1] = p; //先逐位比较出 nxt[1] 的值
    for(int i = 2; i < len; i++)
    {
        p = k + nxt[k] - 1; //定义
        l = nxt[i - k]; //定义
        if(i + l <= p) nxt[i] = l; //如果灰方框小于初始的绿方框,直接确定 nxt[i] 的值
        else
        {
            int j = max(0, p - i + 1);
            while(i + j < len && c[i + j] == c[j]) j++; //否则进行逐位比较
            nxt[i] = j;
            k = i; //此时的 x + nxt[x] - 1 一定刷新了最大值，于是我们要重新赋值 k
        }
    }
}

\(EXT:\)

void exkmp(char *a, char *b)
{
    int la = strlen(a), lb = strlen(b);
    int p = 0, k = 0, l;
    while(p < la && p < lb && a[p] == b[p]) p++; //先算出初值用于递推
    ext[0] = p;
    for(int i = 1; i < la; i++) //下面都是一样的逻辑啦
    {
        p = k + ext[k] - 1;
        l = nxt[i - k];
        if(i + l <= p) ext[i] = l;
        else
        {
            int j = max(0, p - i + 1);
            while(i + j < la && j < lb && a[i + j] == b[j]) j++;
            ext[i] = j;
            k = i;
        }
    }
}

\(\text{IV - AC Automation}\)

You can simply regard The AC Automation as the sum of executing KMP on a Trie Tree.

The key point is the pointer fail of each tree node. It tells you where you should currently skip to after discovering one unequality. (Of course, the pointer fail can be 'skipped' for many times until you got the place.)

#include 
#define _ read()
#define LL long long
#define pii pair 
#define pll pair 
#define Mp make_pair
#define db double
#define eps 1e-7
#define Pi acos(-1)
#define min(x, y) (x < y ? x : y)
#define max(x, y) (x > y ? x : y)
#define lsp p << 1
#define rsp p << 1 | 1
#define lowbit(x) (x & -x)
#define ms(a, x) memset(a, x, sizeof(a))
using namespace std;
const int N = 1e6 + 5; // Check: The value of N

inline void File() {
    freopen("in.txt", "r", stdin);
    freopen("Ans.txt", "w", stdout);
}

inline int read() {
    int x = 0, w = 0; char ch = getchar();
    while(!isdigit(ch)) { w |= ch == 45; ch = getchar(); }
    while(isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    return w ? -x : x;
}

queue  q;
struct AC_Automation {
    int c[N][26], val[N], fail[N], cnt;

    inline void insert(char *s) {
        int len = strlen(s), u = 0;
        for(int i = 0; i < len; i++) {
            int ch = s[i] - 'a';
            if(!c[u][ch]) c[u][ch] = ++cnt;
            u = c[u][ch];
        }
        val[u]++;
    }

    inline void BFS() {
        for(int i = 0; i < 26; i++) {
            if(c[0][i]) fail[c[0][i]] = 0, q.push(c[0][i]);
        }
        while(!q.empty()) {
            int u = q.front(); q.pop();
            for(int i = 0; i < 26; i++) 
                if(c[u][i]) { fail[c[u][i]] = c[fail[u]][i]; q.push(c[u][i]); }
                else c[u][i] = c[fail[u]][i]; // 这里直接将空节点当作失配指针，用于访问的指针赋值为它后相当于直接跳到了失配指针所指的地方，较为简洁。
        }
    }

    inline int query(char *s) {
        int len = strlen(s), u = 0, ans = 0;
        for(int i = 0; i < len; i++) {
            u = c[u][s[i] - 'a']; // 无需再次判断失配
            for(int t = u; t && ~val[t]; t = fail[t]) { ans += val[t]; val[t] = -1; }
        }
        return ans;
    }
}AC;

int n; char p[N];

signed main() {
    File();
    cin >> n;
    for(int i = 1; i <= n; i++) {
        scanf("%s", p);
        AC.insert(p);
    }
    AC.BFS();
    scanf("%s", p);
    printf("%d\n", AC.query(p));
    return 0;
}