AcWing 1368. 最长前缀
原题链接
中等
作者:
123_35
,
2021-05-11 16:22:37
,
所有人可见
,
阅读 262
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
using namespace std;
typedef unsigned long long ULL;
const int N = 200010,M=210,L=15,P=131;
unordered_set<ULL> S;
bool f[N];
string str;
// S hash
ULL h[N],p[N];
ULL get(int l,int r){ // str[l,r] hash
return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
// P 集合 哈希值计算与 存放
string pstr;
while(cin>>pstr&& pstr!="."){
ULL hash=0;
for(int i=0;i<pstr.size();i++){
hash=hash*P+pstr[i];
}
S.insert(hash);
}
// S 哈希值计算
string tmp;
while(cin>>tmp){
str+=tmp;
}
int n=str.size();
p[0]=1; //h[0]=0
for(int i=1;i<=n;i++){
p[i]=p[i-1]*P; // p^i
h[i]=h[i-1]*P+str[i-1];
}
// dp f[i]=能否以i结尾为前缀 0...n
f[0]=true;
int ret=0;
for(int i=1;i<=n;i++){
for(int j=i;j>0 && i-j<10; j--){ //[j,i]
if(S.count(get(j,i)) && f[j-1]){
f[i]=true;
ret=i;
}
}
}
cout<<ret<<endl;
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2100,M=200010;
int son[N][26],idx;
bool cnt[N];
int f[M];
string str;
void insert(string& x){
int p=0;
for(int i=0;i<x.size();i++){
int v=x[i]-'A';
if(!son[p][v]) son[p][v]=++idx;
p=son[p][v];
}
cnt[p]=true;
}
bool query(int ed){ // [...i-1]可以组合出 且 [i,ed] 为前缀
int p=0;
for(int i = ed ; i > ed - 10 && i > 0; --i ){
int v = str[i-1] - 'A';
if(!son[p][v]) return false;
else{
p = son[p][v];
if(cnt[p] && f[i-1]) return true;
}
}
return false;
}
int main()
{
string t;
while(cin >> t,t != "."){
reverse(t.begin(),t.end());
insert(t);
}
string line;
while(cin >> line) str += line;
int ret=0;
f[0] = true;
int n = str.length();
for(int i=1;i<=n;i++){
if(query(i)){
f[i]=true;
ret=i;
}
}
cout<<ret<<endl;
return 0;
}