Submission #682032

#	Time	Username	Problem	Language	Result	Execution time	Memory
682032		_skb_	회문 (APIO14_palindrome)	C++17	0 / 100	25 ms	34916 KiB

palindrome

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;

struct debug {
#define contPrint { *this << "["; \
        int f = 0; for(auto it : x) { *this << (f?", ":""); *this << it; f = 1;} \
        *this << "]"; return *this;}
 
    ~debug(){cerr << endl;}
    template<class c> debug& operator<<(c x) {cerr << x; return *this;}
    template<class c, class d>
    debug& operator<<(pair<c, d> x) {*this << "(" << x.first << ", " << x.second << ")"; 
        return *this;}
    template<class c> debug& operator<<(vector<c> x) contPrint;
#undef contPrint
};

#define dbg(x) "[" << #x << ": " << x << "]  "
#define Wa() cerr << "[LINE: " << __LINE__ << "] -> "; debug() << 
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);

const int N = 3e5 + 5;
int tree[N][26], idx;
int len[N], lnk[N], t;
char ch[N];

void init()
{
    len[1] = -1, lnk[1] = 1;
    len[2] = 0, lnk[2] = 1;
    idx = t = 2;
}

int cnt[N];
i64 ans = 0;

void extend(int p)
{
    while(ch[p - len[t] - 1] != ch[p]) t = lnk[t];
    int x = lnk[t], c = ch[p] - 'a';
    while(ch[p - len[x] - 1] != ch[p]) x = lnk[x];
    if(!tree[t][c]) {
        tree[t][c] = ++idx;
        len[idx] = len[t] + 2;
        lnk[idx] = len[idx] == 1 ? 2 : tree[x][c];
    }
    cnt[idx]++;
    t = tree[t][c];
}

int main() 
{
    init();
    scanf("%s", ch + 1);
    for(int i = 1; ch[i]; i++) {
        extend(i);
    }
    for(int i = idx; i > 2; i--) {
        cnt[lnk[i]] += cnt[i];
    }
    for(int i = 3; i <= idx; i++) {
        ans = max(ans, 1LL * len[i] * cnt[i]);
    }
    printf("%lld\n", ans);
}

Compilation message (stderr)

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

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