oj.uz

Submission #34075

# Submission time Handle Problem Language Result Execution time Memory
34075 2017-11-07T04:24:27 Z DoanPhuDuc Palindromes (APIO14_palindrome) C++
100 / 100
 799 ms 77024 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 76728 KB Output is correct
2 Correct 0 ms 76728 KB Output is correct
3 Correct 0 ms 76728 KB Output is correct
4 Correct 0 ms 76728 KB Output is correct
5 Correct 0 ms 76728 KB Output is correct
6 Correct 0 ms 76728 KB Output is correct
7 Correct 0 ms 76728 KB Output is correct
8 Correct 0 ms 76728 KB Output is correct
9 Correct 0 ms 76728 KB Output is correct
10 Correct 0 ms 76728 KB Output is correct
11 Correct 0 ms 76728 KB Output is correct
12 Correct 0 ms 76728 KB Output is correct
13 Correct 0 ms 76728 KB Output is correct
14 Correct 0 ms 76728 KB Output is correct
15 Correct 0 ms 76728 KB Output is correct
16 Correct 0 ms 76728 KB Output is correct
17 Correct 0 ms 76728 KB Output is correct
18 Correct 0 ms 76728 KB Output is correct
19 Correct 0 ms 76728 KB Output is correct
20 Correct 0 ms 76728 KB Output is correct
21 Correct 0 ms 76728 KB Output is correct
22 Correct 0 ms 76728 KB Output is correct
23 Correct 0 ms 76728 KB Output is correct
24 Correct 0 ms 76728 KB Output is correct
25 Correct 0 ms 76728 KB Output is correct
26 Correct 0 ms 76728 KB Output is correct
27 Correct 0 ms 76728 KB Output is correct
28 Correct 0 ms 76728 KB Output is correct
29 Correct 0 ms 76728 KB Output is correct
30 Correct 0 ms 76728 KB Output is correct
31 Correct 0 ms 76728 KB Output is correct
32 Correct 0 ms 76728 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 76728 KB Output is correct
2 Correct 0 ms 76728 KB Output is correct
3 Correct 0 ms 76728 KB Output is correct
4 Correct 0 ms 76728 KB Output is correct
5 Correct 0 ms 76728 KB Output is correct
6 Correct 0 ms 76728 KB Output is correct
7 Correct 0 ms 76728 KB Output is correct
8 Correct 0 ms 76728 KB Output is correct
9 Correct 0 ms 76728 KB Output is correct
10 Correct 0 ms 76728 KB Output is correct
11 Correct 0 ms 76728 KB Output is correct
12 Correct 0 ms 76728 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 76728 KB Output is correct
2 Correct 6 ms 76728 KB Output is correct
3 Correct 3 ms 76728 KB Output is correct
4 Correct 3 ms 76728 KB Output is correct
5 Correct 9 ms 76728 KB Output is correct
6 Correct 6 ms 76728 KB Output is correct
7 Correct 6 ms 76728 KB Output is correct
8 Correct 3 ms 76728 KB Output is correct
9 Correct 3 ms 76728 KB Output is correct
10 Correct 6 ms 76728 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 76900 KB Output is correct
2 Correct 63 ms 76900 KB Output is correct
3 Correct 56 ms 76900 KB Output is correct
4 Correct 79 ms 76900 KB Output is correct
5 Correct 136 ms 76900 KB Output is correct
6 Correct 116 ms 76900 KB Output is correct
7 Correct 86 ms 76900 KB Output is correct
8 Correct 106 ms 76900 KB Output is correct
9 Correct 89 ms 76900 KB Output is correct
10 Correct 116 ms 76900 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 77024 KB Output is correct
2 Correct 286 ms 77024 KB Output is correct
3 Correct 256 ms 77024 KB Output is correct
4 Correct 286 ms 77024 KB Output is correct
5 Correct 793 ms 77024 KB Output is correct
6 Correct 446 ms 77024 KB Output is correct
7 Correct 323 ms 77024 KB Output is correct
8 Correct 513 ms 77024 KB Output is correct
9 Correct 396 ms 77024 KB Output is correct
10 Correct 799 ms 77024 KB Output is correct
11 Correct 266 ms 77024 KB Output is correct
12 Correct 539 ms 77024 KB Output is correct