选拔赛 hash 字符串匹配哈希算法(白书p374)

hash

Description

dr所在国度的有个奇怪的规定：他们的字母不是a~z，而是用1~1000表示。

利用这个奇怪的规定，dr想出了一个好玩的游戏：首先给出n个字符串（当然每个字符用1~1000表示），然后给出有m个节点的树，节点编号1~m，这棵树以1号节点为根，每个节点都包含一个字符。现在要求用从根节点到其他m-1个节点的链上的字符组成m-1个新字符串（字符的排列顺序为从根到终点的顺序）。

是否这m-1个新字符串中的任意一个串，都与给出的n个字符串中至少一个串匹配呢？

字符串S与字符串T匹配：设len1=∣S∣,len2=∣T∣len1=|S|,len2=|T|len1=∣S∣,len2=∣T∣，则S1=T1,S2=T2,...,Slen1=Tlen1S_{1}=T_{1},S_{2}=T_{2},...,S_{len1}=T_{len1}S1=T1,S2=T2,...,Slen1=Tlen1 且 len1≤len2len1 \leq len2len1≤len2

Input

第一行输入nnn和mmm，表示有nnn个字符串，树的节点数为m(n≤103,m≤2∗105)m(n \leq 10^3,m \leq 2 * 10^5)m(n≤103,m≤2∗105)

接下来nnn行，每行首先输入一个整数kkk，代表字符串长度，然后输入kkk个整数，代表字符串Si(∣Si∣,∑∣Si∣≤2∗105)S_{i}(|Si|,\sum |Si| \leq 2 * 10^5)Si(∣Si∣,∑∣Si∣≤2∗105)

接下来一行，输入mmm个整数CiC_{i}Ci，表示树上第iii个节点上的字符

接下来m−1m-1m−1行，每行输入2个整数u,v(1≤u,v≤m)u,v(1 \leq u,v \leq m)u,v(1≤u,v≤m)，表示uuu和vvv有一条边

Output

输出占一行，都能匹配输出YES，否则输出NO

Sample Input 1

Sample Output 1

YES

思路：运用hash算法将字符串进行哈希，并用unordered_map储存(因为哈希的值会很大，有ull那么大，用普通的数组存不下，故考虑用map，而且没必要排序
，所以用unordered_map提高效率。ps：以前没用过map，这几次遇到的题用map都巨方便，运用桶排序的思维，且可以查询任意类型)。然后用dfs查询所有
字典树出现的串的情况就OK了。
贴一发文钧菊苣的代码

 #include <bits/stdc++.h>

 #define pb push_back

 using namespace std;

 typedef long long ll;

 typedef unsigned long long ull;

 typedef vector<int> VI;

 //head

 const int MX=2e5+;

 const int has=;

 const double eps=1e-;

 int n,m;

 int val[MX];

 VI E[MX];

 unordered_map<ull,int>vis;

 int dfs(int u,int fa,ull h){

     int res=;//在保证了根节点满足条件的情况下的初始值

     for(auto v:E[u]){

         if(v==fa) continue;

         if(!vis[h*has+val[v]]){

             return ;

         }

         res&=dfs(v,u,h*has+val[v]);

     }

     return res;

 }

 int main(){

     scanf("%d%d",&n,&m);

     for(int i=;i<n;i++){//字符串总数

         int k;scanf("%d",&k);

         ull h=;

         for(int j=;j<k;j++){

             int x;scanf("%d",&x);//每串字符的内容

             h=h*has+x;

             vis[h]=;//hash每串字符的前缀串并标记对应hash值

         }

     }

     for(int i=;i<=m;i++) //对应字符

         scanf("%d",&val[i]);

     for(int i=;i<m;i++){//树结构

         int u,v;scanf("%d%d",&u,&v);

         E[u].pb(v);E[v].pb(u);//建树

     }

     ull h=val[];

     if(!vis[h]) puts("NO");

     else{

         if(dfs(,-,h)) puts("YES");

         else puts("NO");

     }

     return ;

 }

巴特西

选拔赛 hash 字符串匹配哈希算法(白书p374)

最新文章

热门文章

巴特西

选拔赛 hash 字符串匹配 哈希算法(白书p374)

最新文章

热门文章

选拔赛 hash 字符串匹配哈希算法(白书p374)