NC20033. [HNOI2004]L语言
描述
输入描述
输入文件第一行是两个正整数n和m，表示字典D中有n个单词，且有m段文章需要被处理。
之后的n行每行描述一个单词，再之后的m行每行描述一段文章。
其中1 ≤ n, m ≤ 20，每个单词长度不超过10，每段文章长度不超过1M。
输出描述
对于输入的每一段文章，你需要输出这段文章在字典D可以被理解的最长前缀的位置。
示例1
输入:
4 3 is name what your whatisyourname whatisyouname whaisyourname
输出:
14 6 0
说明:
整段文章’whatisyourname’都能被理解C++14(g++5.4) 解法, 执行用时: 286ms, 内存消耗: 125848K, 提交时间: 2020-09-06 09:06:38
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
#define re register
const int max_n = 2e6 + 100;
struct node {
bool IsWard = false;
map<char, int> childs;
}ns[max_n];
int sz = 1;
char val[max_n];
inline void insert(string& s) {
int u = 1;
for (re int i = 0;i < s.size();++i) {
if (!ns[u].childs[s[i]])
ns[u].childs[s[i]] = ++sz;
u = ns[u].childs[s[i]];
}ns[u].IsWard = true;
}
bool used[max_n];
inline int search(int st,string& s) {
int u = 1;int ans = st;
for (re int i = st;i < s.size();++i) {
if (!ns[u].childs[s[i]])return ans;
u = ns[u].childs[s[i]];
if (ns[u].IsWard && !used[i]) {
used[i] = true;
ans = max(ans, search(i + 1, s));
}
}return ans;
}
int main() {
ios::sync_with_stdio(0);
int n, m;cin >> n >> m;
string s;
for (re int i = 0;i < n;++i) {
cin >> s;
insert(s);
}for (re int i = 0;i < m;++i) {
cin >> s;
fill(used, used + s.size(), 0);
cout << search(0, s) << endl;
}
}
C++ 解法, 执行用时: 240ms, 内存消耗: 3448K, 提交时间: 2021-12-05 17:05:19
#include<bits/stdc++.h>
using namespace std;
int trie[300][26],tot;
char s[1 << 20 + 1];
bool flag[300],ff[1 << 20 + 1];
int f(){
memset(ff,0,sizeof(ff));
int ans = 0,t,i,j;
ff[0] = 1;
for (i = 0;s[i];i++){
if (ff[i]){
t = 0;
for (j = i + 1;s[j];j++){
t = trie[t][s[j] - 'a'];
if (!t)break;
if (flag[t]){
ans = max(ans,j);
ff[j] = 1;
}
}
}
}
return ans;
}
int main(){
int n,m,r,i,*p;
cin>>n>>m;
while (n--){
cin>>s;
r = 0;
for (i = 0;s[i];i++){
p = &trie[r][s[i] - 'a'];
if (!*p)*p = ++tot;
r = *p;
}
flag[r] = 1;
}
while (m--){
cin>>s + 1;
cout<<f()<<endl;
}
return 0;
}