POJ

POJ3974 Palindrome

題目連結

  • 題意：給定字串，求最長回文字串。
  • 題解：經典 ManaCher 演算法題目。
    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
    73
    74
    #pragma GCC optimize(2)
    #include <iostream>
    #include <cstring>
    #include <string>
    #include <vector>
    using namespace std;
    const int INF = 1e9;
    const int MXN = 1e6 + 5;
    const int MXV = 0;
    #define MP make_pair
    #define PB push_back
    #define F first
    #define S second
    #define FOR(i, L, R) for (int i = L; i != (int)R; ++i)
    #define FORD(i, L, R) for (int i = L; i != (int)R; --i)
    #define IOS                                                                    \
        cin.tie(NULL);                                                             \
        cout.tie(NULL);                                                            \
        ios_base::sync_with_stdio(false);
    char ss[2 * MXN];
    int ma[2 * MXN];
    int si;

    void sol(char *s)
    {
        int sz = strlen(s);
        si = 0;
        ss[si++] = '$';
        ss[si++] = '#';
        FOR(i, 0, sz)
        {
            ss[si++] = s[i];
            ss[si++] = '#';
        }
        // printf("%s\n", ss);
        int mx = 0, id = 0;
        FOR(i, 0, si)
        {
            if (mx > i)
            {
                ma[i] = min(ma[2 * id - i], mx - i);
            }
            else
            {
                ma[i] = 1;
            }
            while (ss[i + ma[i]] == ss[i - ma[i]])
            {
                ++ma[i];
            }
            if (i + ma[i] > mx)
            {
                id = i;
                mx = i + ma[i];
            }
        }
    }

    int main()
    {
        int ti = 0;
        char s[MXN];
        while (scanf("%s", s), strcmp(s, "END"))
        {
            sol(s);
            int mx = 0;
            FOR(i, 0, si)
            {
                // cout << i << ' ' << ma[i] << '\n';
                mx = max(mx, ma[i] - 1);
            }
            cout << "Case " << ++ti << ": " << mx << '\n';
        }
    }

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)

Recommended Posts