字符串哈希:将字符串转化为一个整数(更便于比较),并尽可能做到字符串与整数唯一对应
hash[l...r]=(hash[r]-hash[l-1]*(p^(r-(l-1))))%mod,结果可能为负数,要加模
暴力过kmp:
求出子串s2的hash值,在母串s1里找所有长度为 |s2| 的子串算出其hash值,与s2的hash值比较
具体对于字符串哈希的应用参看https://www.cnblogs.com/Slager-Z/p/7807011.html
字典树模板:
此种模板应用于某前缀在建好的字典树中是否出现
/*Trie树(字典树) 2011.10.10*/ #include <iostream> #include<cstdlib> #define MAX 26 using namespace std; typedef struct TrieNode //Trie结点声明 { bool isStr; //标记该结点处是否构成单词 struct TrieNode *next[MAX]; //儿子分支 }Trie; void insert(Trie *root,const char *s) //将单词s插入到字典树中 { if(root==NULL||*s=='\0') return; int i; Trie *p=root; while(*s!='\0') { if(p->next[*s-'a']==NULL) //如果不存在,则建立结点 { Trie *temp=(Trie *)malloc(sizeof(Trie)); for(i=0;i<MAX;i++) { temp->next[i]=NULL; } temp->isStr=false; p->next[*s-'a']=temp; p=p->next[*s-'a']; } else { p=p->next[*s-'a']; } s++; } p->isStr=true; //单词结束的地方标记此处可以构成一个单词 } int search(Trie *root,const char *s) //查找某个单词是否已经存在 { Trie *p=root; while(p!=NULL&&*s!='\0') { p=p->next[*s-'a']; s++; } return (p!=NULL&&p->isStr==true); //在单词结束处的标记为true时,单词才存在 } void del(Trie *root) //释放整个字典树占的堆区空间 { int i; for(i=0;i<MAX;i++) { if(root->next[i]!=NULL) { del(root->next[i]); } } free(root); } int main(int argc, char *argv[]) { int i; int n,m; //n为建立Trie树输入的单词数,m为要查找的单词数 char s[100]; Trie *root= (Trie *)malloc(sizeof(Trie)); for(i=0;i<MAX;i++) { root->next[i]=NULL; } root->isStr=false; scanf("%d",&n); getchar(); for(i=0;i<n;i++) //先建立字典树 { scanf("%s",s); insert(root,s); } while(scanf("%d",&m)!=EOF) { for(i=0;i<m;i++) //查找 { scanf("%s",s); if(search(root,s)==1) printf("YES\n"); else printf("NO\n"); } printf("\n"); } del(root); //释放空间很重要 return 0; }
A题:
Description
Input
接下来N行每行包含一个字符串
Output
Sample Input
5
abc
aaaa
abc
abcc
12345
Sample Output
4
HINT
字符串哈希基本题
把字符串与整数唯一对应,比较有多少不同的整数即可
此题采用自然溢出方式
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef unsigned long long ull; ull base=131; ull a[10010]; char s[10010]; int n,ans=1; ull hashs(char s[]) { int len=strlen(s); ull ans=0; for (int i=0;i<len;i++) ans=ans*base+(ull)s[i]; return ans&0x7fffffff; } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%s",s); a[i]=hashs(s); } sort(a+1,a+n+1); for (int i=2;i<=n;i++) if (a[i]!=a[i-1]) ans++; printf("%d\n",ans); return 0; }
B题:
Description
Input
输入文件的第一行有一个整数,代表数据组数。接下来是这些数据,以如下格式给出:
第一行是单词W,一个由{'A','B','C',...,'Z'}中字母组成的字符串,保证1<=|W|<=10000(|W|代表字符串W的长度)
第二行是文章T,一个由{'A','B','C',...,'Z'}中字母组成的字符串,保证|W|<=|T|<=1000000。
Output
Sample Input
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN
Sample Output
1
3
0
HINT
字符串哈希思路
此题就是暴力过kmp的实现
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef unsigned long long ull; ull base=131; ull po[100010],hs[100010*100]; char s1[100010],s2[100010*100]; int n,ans=1,T; ull geth(int l,int r)//计算子串对应哈希值 { return (ull)hs[r]-po[r-l+1]*hs[l-1]; } int main() { po[0]=1; for (int i=1;i<=10010-5;i++) po[i]=po[i-1]*base; scanf("%d",&T); while(T--) { scanf("%s%s",s1+1,s2+1); int l1=strlen(s1+1),l2=strlen(s2+1); ull a1=0,ans=0; for (int i=1;i<=l1;i++)//计算出子串对应的哈希值 a1=a1*base+(ull)s1[i]; for (int i=1;i<=l2;i++)//计算出母串的每一部分对应的哈希值 hs[1]--hs[n] hs[i]=hs[i-1]*base+s2[i]; for (int i=1;i+l1-1<=l2;i++)//找母串中每一串长度为|s1|的子串的哈希值,判断与s1的哈希值是否相等 if (a1==geth(i,i+l1-1)) ans++; printf("%d\n",ans); } return 0; }
C题:
Input
Output
Sample Input
banana
band
bee
absolute
acm
#
ba
b
band
abc
Sample Output
2
3
1
0
HINT
此题是对字典树之求前缀在字典中出现次数的实现
#include <stdio.h> #include <string.h> #include <iostream> using namespace std; struct node{ int num; node* next[26]; node() { num=0; memset(next,0,sizeof(next)); } }; node* root=new node(); node* rt; int id,len; void build(char str[15]) { rt=root; len=strlen(str); for(int i=0;i<len;i++) { id=str[i]-'a'; if(rt->next[id]==NULL) rt->next[id]=new node(); rt=rt->next[id]; rt->num++; } } int querry(char str[15]) { rt=root; len=strlen(str); for(int i=0;i<len;i++) { id=str[i]-'a'; if(rt->next[id]==NULL) return 0; rt=rt->next[id]; } return rt->num; } int main() { char str[100]; while(1) { scanf("%s",str); if(str[0]=='#')break; build(str); } while(~scanf("%s",str)) { printf("%d\n",querry(str)); } return 0; }
D题:
找到一个正整数K,使得K与S的异或结果最大。HHM向你请求帮助
Input
输入的第一行是一个整数T(T < 10),表示共有T组数据。
每组数据的第一行输入两个正整数N,M(<1=N,M<=100000),接下来一行,包含N个正整数,代表 Zeus 的获得的集合,之后M行,每行一个正整数S,代表 Prometheus 询问的正整数。所有正整数均不超过2^32。
Output
对于每个询问,输出一个正整数K,使得K与S异或值最大。
Sample Input
2
3 2
3 4 5
1
5
4 1
4 6 5 6
3
Sample Output
Case #1:
4
3
Case #2:
4
HINT
此题就是01字典树模板题 转自https://blog.csdn.net/solardomo/article/details/52168853
01字典树的实现可以看成是把一个数的二进制字符化后插入到一颗一般的字典树中
比如在01字典树种插入3时 相当于在字典树中插入00 …..00011(一共33位,这个根据具体实现不同)
查找最大异或值的时候我们是从最高位 向下贪心查找 贪心策略为:当前查找第k位 二进制数位IDX 如果存在IDX ^ 1的节点 我们就进入这个节点 否则进入IDX节点
贪心策略的证明: 如果这时我们进入了第K位为IDX 的节点 那么 第k位为IDX ^ 1 的节点组成的数 异或X一定更大
最后关于01字典树的使用:
不用关心代码内部是如何实现的
只将01字典树看做是一个数集 我们可以在这个集合中查找和X异或最大的元素
应用:
经常有区间异或和的题目:比如求[l,r]的异或和
由X xor X = 0 ; 0 xor Y = Y;所有【l,r】 = 【1,r】 XOR 【1,l - 1】
这样在一颗加入了r 前的所有前缀异或和的01字典树上查找【1,r】就能得到以r为右边界的最大异或和
01字典树模板
#include<bits/stdc++.h> using namespace std; typedef long long LL; struct node { int num; node *Next[2]; }; void Bulid(node *head, int num) { node *p = head; for(int i=31; i>=0; i--) { int k = (num>>i)&1; if(p->Next[k] == NULL) { node *q = new node(); p->Next[k] = q; } p = p->Next[k]; } p->num = num; } int query(node *head, int num) { node *p = head; for(int i=31; i>=0; i--) { int k = (num>>i)&1; if(p->Next[k^1] != NULL) p = p->Next[k^1]; else p = p->Next[k]; } return p->num; }
AC代码:
#include <bits/stdc++.h> using namespace std; const int maxn=1e5+10; //集合中的数字个数 typedef long long LL; int ch[32 * maxn][2]; //节点的边信息 LL value[32 * maxn]; //节点存储的值 int node_cnt; //树中当前节点个数 inline void init(){ //树清空 node_cnt = 1; memset(ch[0],0,sizeof(ch)); } inline void Insert(LL x){ //在字典树中插入 X //和一般字典树的操作相同 将X的二进制插入到字典树中 int cur = 0; for(int i = 32;i >= 0;--i){ int idx = (x >> i) & 1; if(!ch[cur][idx]){ memset(ch[node_cnt],0,sizeof(ch[node_cnt])); ch[cur][idx] = node_cnt; value[node_cnt++] = 0; } cur = ch[cur][idx]; } value[cur] = x; //最后的节点插入value } inline LL Query(LL x){ //在字典树中查找和X异或的最大值的元素Y 返回Y的值 int cur = 0; for(int i = 32;i >= 0;--i){ int idx = (x >> i) & 1; if(ch[cur][idx ^ 1]) cur = ch[cur][idx ^ 1]; else cur = ch[cur][idx]; } return value[cur]; } int main() { int t; cin>>t; int d=1; while(t--) { int n,m; scanf("%d%d",&n,&m); int i; init(); for(i=1;i<=n;i++) { LL x; scanf("%lld",&x); Insert(x); } printf("Case #%d:\n",d); for(i=1;i<=m;i++) { LL x; scanf("%lld",&x); printf("%lld\n",Query(x)); } d++; } return 0; }