제출 #437653

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
437653		soroush	회문 (APIO14_palindrome)	C++17	100 / 100	427 ms	61220 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 3e5+10;
const ll mod = 1e9+7;
const ll mod2 = 177013;
const ll base = 547;
const ll base2 = 31;

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define ms(x , y) memset(x , y , sizeof x)

int n;
string s;

struct hash{
	string s;
	ll H2[maxn], pw2[maxn];
	ll *h2;
	ll H[maxn], pw[maxn];
	ll *h;
	ll get(int l, int r){
		return (h[r] - (h[l - 1] * pw[r - l + 1])% mod + mod)%mod;
	}
	ll get2(int l, int r){
		return (h2[r] - (h2[l - 1] * pw2[r - l + 1])%mod2 + mod2)%mod2;
	}
	pair < ll, ll > Get(int l , int r){
		return pair < ll, ll >(get(l ,r) , get2(l ,r));
	}
	void init(string S){
		s = S;
		pw[0] = 1;
		for(int i = 1 ; i < maxn ; i ++)
			pw[i] = (pw[i - 1] * base)%mod;
		pw2[0] = 1;
		for(int i = 1 ; i < maxn ; i ++)
			pw2[i] = (pw2[i - 1] * base2)%mod2;
		h = &H[1];
		for(int i = 0 ; i < n ; i ++)	
			h[i] = ((h[i - 1] * base)%mod + s[i] - 'a' + 1)%mod;
		h2 = &H2[1];
		for(int i = 0 ; i < n ; i ++)	
			h2[i] = ((h2[i - 1] * base2)%mod2 + s[i] - 'a' + 1)%mod2;
	}
}h, hr;

vector < int > q[maxn];

int sa[maxn];
int rk[maxn];
int tp[maxn];
int cnt[maxn];
int lcp[maxn];

void SA(string &s){
	int A = 'z' , p = 0 , n = s.size();
	if(n == 1){
		sa[0] = rk[0] = 0;
		return;
	}
	for(int i = 0 ; i < n ; i ++)
		sa[i] = i , rk[i] = s[i];
	for(int j = 1 ; p < n - 1 ; j<<=1){
		p = 0;
		int k = (j>>1);
		for(int i = n - k ; i < n ; i ++)
			tp[p ++ ] = i;
		for(int i = 0 ; i < n ; i ++)
			if(sa[i] >= k)
				tp[p ++] = sa[i] - k;
		for(int i = 0 ; i <= A ; i ++)
			cnt[i] = 0;
		for(int i = 0 ; i < n ; i ++)
			cnt[rk[i]] ++;
		for(int i = 1 ; i <= A ; i ++)
			cnt[i] += cnt[i - 1];
		for(int i = n - 1 ; i >= 0 ; i --)
			sa[--cnt[rk[tp[i]]]] = tp[i];
		swap(rk , tp);
		rk[sa[0]] = p = 0;
		for(int i = 1 ; i < n ; i ++)
			p += (tp[sa[i - 1]]!=tp[sa[i]] || sa[i - 1] + k  >= n ||
			 tp[sa[i - 1]+k] != tp[sa[i] + k]) , rk[sa[i]] = p;
		A = p;
	}
}

vector < int > mrg[maxn];
int p[maxn], sz[maxn];

int gp(int v){
	return ((p[v] != -1) ? p[v] = gp(p[v]) : v);
}

void merge(int u, int v){
	if((u = gp(u)) == (v = gp(v)))
		return;
	sz[v] += sz[u];
	p[u] = v;
	
}

void LCP(string &s){
	for(int i = 0 , k = 0 ; i < (int)s.size() ; i ++){
		if(rk[i] == 0)continue;
		if(k) k --;
		while(s[i + k] == s[sa[rk[i] - 1] + k]) k ++;
		lcp[rk[i]] = k;
	}
}

void chk(int x){
	int l = 0, r = n;
	while(r - l > 1){
		int mid = (l + r) / 2;
		if(x + mid < n and x - mid > -1 and h.get(x - mid , x + mid) == hr.get(n - (x + mid) - 1 , n - (x - mid) - 1))
			l = mid;
		else 
			r = mid;
	}
	q[1 + 2 * l].pb(x - l);
	if(x > 0){
		int l = 0 , r = n ;
		if(s[x] ^ s[x - 1])return;
		while(r - l > 1){
			int mid = (l + r) / 2;
			if(x + mid < n and x - mid - 1 > -1 and h.get(x - mid - 1 , x + mid) == hr.get(n - (x + mid) - 1 , n - (x - mid - 1) - 1))
				l = mid;
			else 
				r = mid;
		}
		q[2 + 2 * l].pb(x - 1 - l);
	}
}


int32_t main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> s;
	n = s.size();
	h.init(s);
	reverse(s.begin(),s.end());
	hr.init(s);
	reverse(s.begin(),s.end());
	SA(s);
	LCP(s);
	ms(p, -1);
	for(int i = 0 ; i < n ; i ++)sz[i] = 1;
	for(int i = 1 ; i < n ; i ++)
		mrg[lcp[i]].pb(i - 1);
	for(int i = 0 ; i < n ; i ++)
		chk(i);
	ll ans = 0;
	for(int i = n ; i >= 0 ; i --){
		for(int x : mrg[i])
			merge(sa[x], sa[x + 1]);
		for(int x : q[i]){
			ans = max(ans, sz[gp(x)] * 1ll * i);
		}
	}
	cout << ans;
	return(0);
}

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