제출 #554634

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
554634		kwongweng	회문 (APIO14_palindrome)	C++17	100 / 100	67 ms	71312 KiB

palindrome

/*
Solution for APIO 2014 - Palindrome
Tags : palindromic tree
*/
 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second
 
ll MOD = 1000000007;
 
ll power(ll base, ll n){
	if (n == 0) return 1;
	if (n == 1) return base;
	ll halfn = power(base, n/2);
	if (n % 2 == 0) return (halfn * halfn) % MOD;
	return (((halfn * halfn) % MOD) * base) % MOD;
}
 
ll inverse(ll n){
	return power(n, MOD-2);
}
 
ll add(ll a, ll b){
	return (a+b) % MOD;
}
 
ll mul(ll a, ll b){
	a %= MOD;
	return (a*b) % MOD;
}
 
ll gcd(ll a, ll b){
    if (a == 1) return 1;
    if (a == 0) return b;
    return gcd(b%a, a);
}

string s;
const int N = 300031;

struct Node{
    int len; 
    int nxt[26]; 
    vi edges; 
    int sufflink; 
    int cnt; 

    //len = length of palindrome
    //nxt[i] = palindrome formed by adding ith alphabet to current palindrome
    //edges = list of palindromes that contains this palindrome as longest proper suffix that is a palindrome
    //edges can also be defined as "inverse" of sufflink
    //sufflink = longest palindrome that is proper suffix of current palindrome
    //cnt = # occurence of this palindrome
} tree[N];

int num, suff;
//num = number of distinct palindromes currently found
//suff = currently the longest palindrome that is a suffix to this string

//initialise the tree
void init(){
    num = 2; suff = 2;
    tree[1].len = -1; tree[1].sufflink = 1;
    tree[2].len = 0; tree[2].sufflink = 1;
    tree[1].edges.pb(2);
}

// at most O(N) distinct palindromic substrings
void add(int pos){
    int cur = suff, curlen = 0;
    int letter = s[pos]-'a';

    while (true){
        curlen = tree[cur].len;
        if (pos-curlen-1 >= 0 && s[pos-curlen-1] == s[pos]){
            break;
        }
        cur = tree[cur].sufflink;

        //iterate sufflink until palindrome ending at pos is found
        //this will be the longest palindrome that ends at pos
    }

    // This palindrome has existed
    if (tree[cur].nxt[letter]){
        suff = tree[cur].nxt[letter];
        tree[suff].cnt++;
        return;
    }
    
    //new palindrome is found
    num++;
    suff = num;
    tree[num].len = tree[cur].len + 2;
    tree[num].cnt = 1;
    tree[cur].nxt[letter] = num;

    //find the sufflink for tree[num]
    if (tree[num].len == 1){
        tree[num].sufflink = 2;
        tree[2].edges.pb(num);
        return;
    }

    while (true){
        cur = tree[cur].sufflink;
        curlen = tree[cur].len;
        if (pos-curlen-1 >= 0 && s[pos-curlen-1] == s[pos]){
            int val = tree[cur].nxt[letter];
            tree[num].sufflink = val;
            tree[val].edges.pb(num);
            break;

            //val exists since:
            //consider xAx to be the new palindrome (tree[num])
            //if xBx is a proper suffix of xAx,
            //we can write xAx = xA'xBx = xBxA'x. (symmetry of palindromes)
            //this means we have found xBx before.
            //so val exists.
        }
    }    
}

ll ans = 0;
void dfs(int u){
    for (int v : tree[u].edges){
        dfs(v);
        tree[u].cnt += tree[v].cnt;
        //palindrome u is the longest palindromic suffix of v
    }
    ans = max(ans, (ll) tree[u].cnt * (ll) tree[u].len);
}

void solve(){
    cin >> s;
    int n = s.size();
    init();
    FOR(i,0,n){
        add(i);
    }
    dfs(1);
    cout << ans;
    return;
}
 
int main() {
    ios::sync_with_stdio(false);
    int TC = 1;
    //cin >> TC;
    FOR(i, 1, TC+1){
        //cout << "Case #" << i << ": ";
        solve();
    }
}

컴파일 시 표준 에러 (stderr) 메시지

palindrome.cpp:10: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   10 | #pragma GCC optimization ("Ofast")
      | 
palindrome.cpp:11: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   11 | #pragma GCC optimization ("unroll-loops")
      |

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