P7537 [COCI2016-2017#4] Rima

トライ木と木上の動的計画法

問題の制約を整理すると、文字列の末尾に文字を追加したり、置換したり、削除したりできることが分かります。この操作は、あるポイントで削除が起こり、その後追加が続くため、単峰性を持ちます。両端の処理は対称なので、片側だけ考えれば十分です。文字列を逆転させてトライ木に挿入し、木上のDPで各ノードの部分木に何個の文字列が連結できるかを計算します。ここで、ノードuにおける部分木の文字列数をf[u]と定義し、遷移は容易に導けます。

答えの算出には、最も短い文字列の終端位置を全探索します。その際、子ノードから最大の2つのf[v]を取り出し、それらを結合して貢献を計算します。

計算量はO(Σ|s_i|)です。

#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define fi first
#define se second
#define pb push_back

using i64 = long long;
using ull = unsigned long long;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 5e5 + 10;

int n, tot, ans = 1;
int tr[28 * N][28], ed[28 * N], f[28 * N];

void insert(std::string s) {
	int u = 0;
	for(int i = s.length() - 1; i >= 0; i--) {
		int c = s[i] - 'a';
		if(!tr[u][c]) tr[u][c] = ++tot;
		u = tr[u][c];
	}
	ed[u]++;
}
void dfs(int u) {
	int cnt = 0;
	for(int i = 0; i < 26; i++) {
		if(tr[u][i]) {
			dfs(tr[u][i]);
			if(ed[tr[u][i]]) f[u] = std::max(f[u], f[tr[u][i]]);
			cnt += ed[tr[u][i]];
		}
	} 
	f[u] += std::max(0, cnt - 1) + ed[u];
}
void dfs2(int u) {
	int max = 28 * N - 1, max2 = 28 * N - 1, cnt = 0;
	for(int i = 0; i < 26; i++) {
		if(tr[u][i]) {
			if(f[max] < f[tr[u][i]] && ed[tr[u][i]]) max = tr[u][i];
			cnt += ed[tr[u][i]];
		}
	}
	for(int i = 0; i < 26; i++) {
		if(tr[u][i]) if(f[max2] < f[tr[u][i]] && tr[u][i] != max && ed[tr[u][i]]) max2 = tr[u][i];
	}
	for(int i = 0; i < 26; i++) {
		if(tr[u][i]) dfs2(tr[u][i]);
	}
	if(max != 28 * N - 1 && max2 != 28 * N - 1) ans = std::max(ans, f[max] + f[max2] + (cnt - 2) + ed[u]);
	else if(max != 28 * N - 1) ans = std::max(ans, f[max] + (cnt - 1) + ed[u]);
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
	std::cin >> n;

	for(int i = 1; i <= n; i++) {
		std::string s;
		std::cin >> s;
		insert(s);
	}	

	dfs(0);
	dfs2(0);

	std::cout << ans << "\n";

	return 0;
}

簡略版：

#include
#define pii std::pair
#define fi first
#define se second
#define pb push_back

using i64 = long long;
using ull = unsigned long long;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 5e5 + 10;

int n, tot, ans = 1;
int tr[29 * N][29], ed[29 * N], f[29 * N];

void insert(std::string s) {
int u = 0;
for(int i = s.length() - 1; i >= 0; i--) {
int c = s[i] - 'a';
if(!tr[u][c]) tr[u][c] = ++tot;
u = tr[u][c];
}
ed[u]++;
}
void dfs(int u) {
int max = 0, max2 = 0, cnt = 0;
for(int i = 0; i < 26; i++) {
if(tr[u][i]) {
int v = tr[u][i];
dfs(v);
if(max < f[v]) max2 = max, max = f[v];
else if(max2 < f[v]) max2 = f[v];
cnt += ed[v];
}
}
if(ed[u]) f[u] = max + std::max(cnt, 1);
ans = std::max(ans, max + max2 + ed[u] + std::max(cnt - 2, 0));
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);

std::cin >> n;

for(int i = 1; i <= n; i++) {
std::string s;
std::cin >> s;
insert(s);
}

dfs(0);

std::cout << ans << "\n";

return 0;
}