yukicoder : No.2606 Mirror Relay

以前作ったのにすっかり忘れてた。
https://yukicoder.me/problems/no/2606

問題

文字列Sが与えられる。

文字列Tを作ったとき、以下のスコアが与えられる。
Tのa文字のprefixが回文でありかつS中にb回あるとき、a*bがスコアに加算される。
最適なTを指定すると、総スコアの最大値はどうなるか。

解法

Sに対応するPalindromicTreeを作る。
この木の各ノードには、Sにおける出現頻度とprefixとなる最長の回文へのリンクが与えられる。

よって、このリンクをたどることで各ノードに対応する回文とスコアがわかるうえ、prefixの回文に対するスコアの総和もわかる。

struct PalindromicTree {
	struct node {
		map<char,int> next;
		int len, sufflink,num,first;
		ll val=0;
	};
	string S;
	vector<node> V;
	int n,s; // num,suff
	
	bool add(int pos) {
		char ch=S[pos];
		int c=s, cl=0;
		while(1) {
			cl=V[c].len;
			if(pos-1-cl>=0 && S[pos-1-cl]==ch) break;
			c=V[c].sufflink;
		}
		
		if(V[c].next.count(ch)) {
			s = V[c].next[ch];
			V[s].num++;
			return false;
		}
		
		s=++n;
		V[n].len=V[c].len+2;
		V[n].first=pos;
		V[c].next[ch]=n;
		
		if(V[n].len==1) { // even length
			V[n].sufflink=2;
			V[n].num=1;
			return true;
		}
		
		while(1) {
			c=V[c].sufflink;
			cl=V[c].len;
			if(pos-1-cl>=0 && S[pos-1-cl]==ch) {
				V[n].sufflink=V[c].next[ch];
				break;
			}
		}
		V[n].num++;
		return true;
	}
	
	void init(string S) {
		this->S=S;
		V.clear();
		V.resize(S.size()+10);
		
		n=s=2;
		V[1].first=V[2].first=-1;
		V[1].len=-1;
		V[2].len=0;
		V[1].sufflink=V[2].sufflink=1;
	}
};

int N;
string S;
PalindromicTree pt;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	pt.init(S);
	ll ma=0;
	FOR(i,N) pt.add(i);
	for(i=pt.V.size()-1;i>=3;i--) if(pt.V[i].sufflink) {
		pt.V[pt.V[i].sufflink].num+=pt.V[i].num;
	}
	for(i=3;i<pt.V.size();i++) {
		pt.V[i].val=1LL*pt.V[i].len*pt.V[i].num+pt.V[pt.V[i].sufflink].val;
		ma=max(ma,pt.V[i].val);
	}
	cout<<ma<<endl;
}

まとめ

PalindromicTreeって以前★5だった気がするけどもう★4なのか。