知识点总结

Manacher1 Manacher2 回文自动机/回文树

Problems

Hdu5785 Interesting(Manacher)

Hdu5785 Interesting(Manacher)

Hdu5157 Harry and magic string(回文自动机)

Hdu5157 Harry and magic string(回文自动机)

Hdu5421 Victor and String（回文自动机）

Hdu5421 Victor and String（回文自动机）

Hdu3068 最长回文

Manacher模板题

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>

using namespace std;

const int Maxn = 2 * 11000000 + 100;

char S[Maxn];
char A[Maxn];
int P[Maxn];

int N;

inline void Input ()
{
    N = strlen(S + 1);
    for (int i = 1; i <= N; ++i)
        A[i * 2] = S[i], A[i * 2 - 1] = '#';
    A[0] = '!', A[2 * N + 1] = '#';
    A[2 * N + 2] = '*';
    N = 2 * N + 1;
}

inline void Solve ()
{
    int id = 0, Max = 0;
    int Ans = 0;
    for (int i = 0; i <= N; ++i) P[i] = 0;
    for (int i = 1; i <= N; ++i)
    {
        if (i < Max)
            P[i] = min(Max - i, P[2 * id - i]);
        else P[i] = 1;
        while (A[i + P[i]] == A[i - P[i]]) P[i] ++;
        //cout<<P[i]<<endl;
        if (Max < i + P[i] - 1)
        {
            Max = i + P[i] - 1;
            id = i;
        }
        Ans = max(Ans, P[i] - 1);
    }
    cout<<Ans<<endl;
}

int main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    while (~scanf("%s", S + 1))
    {
        Input();
        Solve();
    }
    return 0;
}

[Apio2014]回文串

回文自动机模板题 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int Maxn = 300000 + 100;

char S[Maxn];
int N, cnt;

struct tree
{
    int cnt, ch[30], len, fail;
};

namespace PAM
{
    tree Tree[Maxn];
    int root0, root1, now;

    inline void init ()
    {
        cnt = -1;
        root0 = ++cnt, root1 = ++cnt;
        Tree[root0].fail = root1;
        Tree[root0].len = 0;
        Tree[root1].len = -1;
    }

    inline int get_fail (int now, int i)
    {
        while (S[i - Tree[now].len - 1] != S[i]) now = Tree[now].fail;
        return now;
    }

    inline void add (int c, int i)
    {
        now = get_fail(now, i);
        if (!Tree[now].ch[c])
        {
            int x = ++cnt;
            Tree[x].len = Tree[now].len + 2;
            Tree[x].fail = Tree[get_fail(Tree[now].fail, i)].ch[c];
            Tree[now].ch[c] = x;
        }
        now = Tree[now].ch[c];
        Tree[now].cnt ++;
    }
}

int main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif

    scanf("%s", S);
    PAM :: init();
    int N = strlen(S);
    for (int i = 0; i < N; ++i)
        PAM :: add(S[i] - 'a', i);

    LL Ans = 0;
    for (int i = cnt; i > 1; --i)
    {
        PAM :: Tree[PAM :: Tree[i].fail].cnt += PAM :: Tree[i].cnt;
        Ans = max(Ans, (LL)((LL)PAM :: Tree[i].cnt * PAM :: Tree[i].len));
    }
    cout<<Ans<<endl;
    return 0;
}

BZOJ2565 最长双回文串（Manacher）

BZOJ2565 最长双回文串（Manacher）