Submission #34075

#	Time	Username	Problem	Language	Result	Execution time	Memory
34075		DoanPhuDuc	Palindromes (APIO14_palindrome)	C++98	100 / 100	799 ms	77024 KiB

palindrome

#include <bits/stdc++.h>

#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n)  { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }
#define BitCount(x) __builtin_popcount(x)

using namespace std;

typedef long long LL;

const int N = 3e5 + 10;

int n;

char S[N];

struct PalindromeTree {
    struct Node {
        int l, r, Len, suffLink;
        int nxt[26];
    } T[N];
    int TSize, suff;
    void Init() {
        TSize = suff = 2;
        T[1].Len = -1; T[1].suffLink = 1;
        T[2].Len = +0; T[2].suffLink = 1;
    }
    void AddLetter(int pos) {
        int cur = suff;
        int ltr = S[pos] - 'a';
        while (true) {
            int l = T[cur].Len;
            if (pos - l - 1 >= 1 && S[pos - l - 1] == S[pos]) break;
            cur = T[cur].suffLink;
        }
        if (T[cur].nxt[ltr]) {
            suff = T[cur].nxt[ltr];
            return;
        }
        suff = ++TSize;
        T[TSize].Len = T[cur].Len + 2;
        T[TSize].l   = pos - T[TSize].Len + 1;
        T[TSize].r   = pos;
        T[cur].nxt[ltr] = TSize;
        if (T[TSize].Len == 1) {
            T[TSize].suffLink = 2;
            return;
        }
        while (true) {
            cur = T[cur].suffLink;
            int l = T[cur].Len;
            if (pos - l - 1 >= 1 && S[pos - l - 1] == S[pos]) {
                T[TSize].suffLink = T[cur].nxt[ltr];
                break;
            }
        }
    }
} PT;

struct SuffixArray {
    int n;
    int SA[N], LCP[N], num[N], L[N], R[N], C[N], pos[N];
    char S[N];
    bool mark[N];
    void Init(string T) {
        n = T.size() + 1;
        FOR(i, 1, n - 1) S[i] = T[i - 1];
        S[n] = 0;
        BuildSA();
        BuildLCP();
    }
    void BuildSA() {
        memset(C, 0, sizeof C);
        FOR(i, 1, n) C[S[i]]++;
        FOR(i, 1, 255) C[i] += C[i - 1];
        FOD(i, n, 1) R[C[S[i]]--] = i;
        FOR(i, 2, n) mark[i] = S[R[i]] != S[R[i - 1]]; mark[1] = true;
        for (int k = 1; k <= n; k <<= 1) {
            int d = 0;
            FOR(i, 1, n) {
                if (mark[i]) ++d; num[R[i]] = d;
                L[i] = (R[i] - k - 1 + 3 * n) % n + 1;
            }
            FOR(i, 0, n) C[i] = 0;
            FOR(i, 1, n) C[num[L[i]]]++;
            FOR(i, 1, n) C[i] += C[i - 1];
            FOD(i, n, 1) R[C[num[L[i]]]--] = L[i];
            int p = -1;
            FOR(i, 1, n) {
                int x = num[(R[i] + k - 1 + 3 * n) % n + 1];
                mark[i] = p != x || num[R[i]] != num[R[i - 1]];
                p = x;
            }
        }
        n = n - 1;
        FOR(i, 0, n) SA[i] = R[i + 1];
    }
    void BuildLCP() {
        FOR(i, 1, n) pos[SA[i]] = i;
        int x = 0; LCP[0] = 0;
        FOR(i, 1, n) {
            int j = SA[pos[i] - 1];
            while (S[i + x] == S[j + x]) ++x;
            LCP[pos[i]] = x;
            x = max(x - 1, 0);
        }
    }
} SA;

struct RMQ {
    static const int LG = 20;
    int lg[N];
    int spT[N][LG + 5];
    void Init() {
        FOR(i, 1, n) spT[i][0] = SA.LCP[i];
        for (int j = 1; 1 << j <= n; ++j)
            for (int i = 1; i + (1 << j) - 1 <= n; ++i)
                spT[i][j] = min(spT[i][j - 1], spT[i + (1 << (j - 1))][j - 1]);
        for (int i = 0; 1 << i <= n; ++i) lg[1 << i] = i;
        FOR(i, 1, n) if (!lg[i]) lg[i] = lg[i - 1];
    }
    int LCP(int l, int r) {
        int k = lg[r - l + 1];
        return min(spT[l][k], spT[r - (1 << k) + 1][k]);
    }
} RMQ;

int FindLeft(int i, int Len) {
    int l = 1, r = i - 1, f = i;
    while (l <= r) {
        int m = (l + r) >> 1;
        if (RMQ.LCP(m + 1, i) >= Len) {
            f = m;
            r = m - 1;
        } else l = m + 1;

    }
    return f;
}

int FindRight(int i, int Len) {
    int l = i + 1, r = n, f = i;
    while (l <= r) {
        int m = (l + r) >> 1;
        if (RMQ.LCP(i + 1, m) >= Len) {
            f = m;
            l = m + 1;
        } else r = m - 1;
    }
    return f;
}

int main() {
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // LOCAL
    scanf("%s", S + 1); n = strlen(S + 1);
    PT.Init();
    FOR(i, 1, n) PT.AddLetter(i);
    SA.Init(string(S + 1, S + n + 1));
    RMQ.Init();
   // PR(SA.SA, n);
   // PR(SA.LCP, n);
    LL ans = 0;
    FOR(i, 3, PT.TSize) {
        int k = PT.T[i].l, Length = PT.T[i].r - PT.T[i].l + 1;
        int l = FindLeft(SA.pos[k], Length), r = FindRight(SA.pos[k], Length);
        ans = max(ans, (LL)(r - l + 1) * Length);
    }
    printf("%lld", ans);

    return 0;
}

Compilation message (stderr)

palindrome.cpp: In member function 'void SuffixArray::BuildSA()':
palindrome.cpp:78:28: warning: array subscript has type 'char' [-Wchar-subscripts]
         FOR(i, 1, n) C[S[i]]++;
                            ^
palindrome.cpp:80:30: warning: array subscript has type 'char' [-Wchar-subscripts]
         FOD(i, n, 1) R[C[S[i]]--] = i;
                              ^
palindrome.cpp: In function 'int main()':
palindrome.cpp:162:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", S + 1); n = strlen(S + 1);
                       ^

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27