Submission #570129

#	Time	Username	Problem	Language	Result	Execution time	Memory
570129		_Bohemian	회문 (APIO14_palindrome)	C++17	47 / 100	1092 ms	33024 KiB

palindrome

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> PII;
const ll mx = 3e5+10;

const int A = 26;
const int N = 300010;

char s[N]; // 1-Indexed

int last, ptr, nxt[N][A], link[N], len[N], occ[N], depth[N], end_At[N];

void feed(int At) {
    while(s[At-len[last]-1]!=s[At])
        last = link[last];

    int ch = s[At]-'a', temp = link[last];

    while(s[At-len[temp]-1]!=s[At])
        temp = link[temp];

    if(!nxt[last][ch]) {
        nxt[last][ch] = ++ptr, len[ptr] = len[last]+2;
        link[ptr] = len[ptr]==1?2:nxt[temp][ch];
        depth[ptr] = depth[link[ptr]] + 1;
    }
    last = nxt[last][ch], ++occ[last];
    end_At[At] = depth[last];
}

int main() {

    int t = 1;
    while(t--) {
        len[1] = -1, link[1] = 1, len[2] = 0, link[2] = 1;
        ptr = last = 2;
        int n;
        scanf("%s", s + 1);
        for(int i=1; n = strlen(s+1), i<=n; i++) {
            feed(i);
        }
        for(int i = ptr; i > 2; i--) occ[link[i]] += occ[i];

        ll Ans = 0;
        for(int i=1; i<=ptr; i++) {
            ll p = len[i] * occ[i];
            Ans = max(Ans,p);
        }
        cout<<Ans<<endl;
    }
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         scanf("%s", s + 1);
      |         ~~~~~^~~~~~~~~~~~~

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