AcWing 1368. 最长前缀——O(10*len(s))
原题链接
中等
作者:
虹之间
,
2020-12-27 20:42:00
,
所有人可见
,
阅读 528
#include <iostream>
#include <unordered_set>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int f[N]; // f[i]表示s[0...i]能否由p组成
int main()
{
ios::sync_with_stdio(false);
unordered_set<string> p;
string s;
int l = 0;
while(cin >> s){
if(s == ".") break;
reverse(s.begin(), s.end());
l = max(l, (int)s.length());
p.insert(s);
}
s = "";
string item;
while(cin >> item){
s += item;
}
s = "#" + s;
f[0] = 1;
int res = 0;
for(int i = 1; i <= (int)s.length(); i ++ ){
string temp = "";
for(int j = i; j > 0 && j > i - l; j -- ){
temp += s[j];
if(f[j - 1] == 1 && p.count(temp)) {
f[i] = 1;
break;
}
}
if(f[i]) res = i;
}
cout << res << endl;
return 0;
}