$2022ICPC$西安站的一道具有一定思维的签到题
一个字符串$t$是$perfect$的,当且仅当它的每一个子串都在给定的$n$个串中出现,往往这种都需要去挖掘$perfect$具有哪些性质,设字符串$t$长度为$m$,下标从$0$开始,本题中最关键的性质如下:
字符串$t$是$perfect$的 $\Leftrightarrow$ $t[0, m - 2]$和$t[1, m - 1]$ 均是$perfect$的
简要证明:$t[0, m - 2]$和$t[1, m - 1]$所有子串的并集与字符串$t$的所有子串是相同的,故两者等价
代码实现:按照字符串长度从小到大进行排序,用一个$set$存取所有$perfect$的字符串,从前往后扫描,若当前字符串长度为$1$,则是$perfect$的,加入到$set$中,否则判断$t[0, m - 2]$和$t[1, m - 1]$ 是否均是$perfect$的,若是,也加入到$set$中
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin >> n;
vector<string> s(n);
for (int i = 0; i < n; i ++ ) cin >> s[i];
sort(s.begin(), s.end(), [&] (string a, string b)
{
return a.size() < b.size();
});
set<string> S;
int res = 0;
for (int i = 0; i < n; i ++ )
{
int m = s[i].size();
if (m == 1)
{
S.insert(s[i]);
res = max(res, 1);
}
else
{
if (S.count(s[i].substr(0, m - 1)) && S.count(s[i].substr(1, m - 1)))
{
res = max(res, m);
S.insert(s[i]);
}
}
}
cout << res << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
while (T -- ) solve();
return 0;
}