免费的软件网站,手机wap网站免费建站,网站tdk建设,网站建设在哪里申请正题
luogu 3879 ybtoj Trie-4 题目大意
给你n篇文章#xff0c;还有m个单词#xff0c;问你这些单词在哪几篇文章中出现过 解题思路
对文章中的单词建Trie#xff0c;然后那查询的单词去匹配 代码
#includemap
#includevector
#includecstdio
…正题
luogu 3879 ybtoj Trie-4 题目大意
给你n篇文章还有m个单词问你这些单词在哪几篇文章中出现过 解题思路
对文章中的单词建Trie然后那查询的单词去匹配 代码
#includemap
#includevector
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 500100
#define mp(x,y) make_pair(x,y)
using namespace std;
int n, m, w;
char s[N];
mappairint, int, intto;//直接存会MLE用map以时间换空间
vectorint a[N];
void insert(char* s, int v)//存单词
{int now 0, y, n strlen(s1);for (int i 1; i n; i){y s[i] - a;if (!to[mp(now, y)]) to[mp(now, y)] w;now to[mp(now, y)];}if (!a[now].size()) a[now].push_back(v);else if (a[now][a[now].size() - 1] ! v) a[now].push_back(v);//不重复存
}
void ask(char* s)
{int now 0, y, n strlen(s1), p 0;for (int i 1; i n; i){y s[i] - a;if (!to[mp(now, y)]){p 1;break;}else now to[mp(now, y)];}if (p || !a[now].size()) puts( );else{printf(%d, a[now][0]);for (int i 1; i a[now].size(); i)printf( %d, a[now][i]);putchar(10);}return;
}
int main()
{scanf(%d, n);for (int i 1; i n; i){scanf(%d, m);while(m--){scanf(%s, s1);insert(s, i);}}scanf(%d, n);while(n--){scanf(%s, s1);ask(s);}return 0;
}
