Link

ICPC2022Xian G Perfect Word

Question

给出 \(n\) 个串，我们称 \(t\) 串是 "good" 当且仅当 \(t\) 的所有子串都在 \(n\) 个串中出现过

问最长的 "good" 的串的长度

Solution

由于所有串的子串个数为 \(L\times (L+1)/2\) ， \(L\) 为串的长度

所以 ”good“ 串 的长度 不会大于 大约 350

有很容易发现一个性质 ，一个 "good" 串 的所有子串都是 “good” 子串

所以暴力枚举每个串的所有子串，判断是不是 “good” 串

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 2e5 + 5;
ll Tex = 1, n, ans = 1;
string s[MAXN];
map<string, ll> mp;
bool cmp(string xx, string yy)
{
	return xx.size() < yy.size();
}
void AC()
{
	cin >> n;
	for(int i = 1; i <= n; i ++)
		cin >> s[i];
	sort(s + 1, s + n + 1, cmp);
	for(int i = 1; i <= n; i ++)
	{
		if(s[i].size() == 1) mp[s[i]] = 1;
		else
		{
			if(s[i].size() > 350) continue;
			string l, r;
			for(int j = 0; j < s[i].size() - 1; j ++)
				l.push_back(s[i][j]);
			for(int j = 1; j < s[i].size(); j ++)
				r.push_back(s[i][j]);
			if(mp[l] && mp[r])
			{
				ans = max(ans, (ll)s[i].size());
				mp[s[i]] = 1;
			}
		}
	}
	cout << ans << endl;
}
int main()
{
	ios::sync_with_stdio(false);
//	cin >> Tex;
	while(Tex --) AC();
	return 0;
}