字符串哈希&子串匹配
字符串哈希 字符串哈希就是将一个字符串映射为一个整数,该整数就可以用于vis标记有没有出现过,就不用遍历所有字符串了。
哈希公式:
hash[i] = hash[ i - 1 ] *p+ id( s[i] )
其中id(x)为x-‘a’+1或者x的ask码,p为质数。例如对abcd哈希:
可以看到,在求abcd的过程,也顺便把abcd前缀的哈希值求了一遍,那么现在如果要获得abcd子串的哈希值呢,例如要获得bc的哈希值,要从b开始哈希一遍吗?其实是有o(1)的算法的:
来看看 abcd 如果从1开始标号,s[1]=a,s[2]=b,s[3]=c,s[4]=d,为推导方便省略id(),那么:
hash [1]=s[1];
hash [2]=s[1]*p+s[2]
hash [3]=s[1]*p2+s[2]*p+s[3]
hash [4]=s[1]*p3+s[2]*p2+s[3]*p+s[4]
现在要求s2s3的哈希值,根据定义就是s[2]*p+s[3],现在观察一下上面四条式子,很容易看出hash[ 3 ]- hash[ 1 ]*p2就等于hash[s2s3]了。
可以推广出公式:在字符串s中,第l到r位子串的哈希值为:hash[r]-hash[l-1]*pr-l+1,所以,只要我们得到了一个字符串的哈希值,就可以在o(1)的时间内得到它的子串的哈希值。
例题华工赛字符串题:https://ac.nowcoder.com/acm/contest/625/K
意思是给定一个字符串,有q次查询,每次查询给字符串设个断点,计算断点前的字符串的子串在断点后的字符串出现的次数和。
例如ababa,对于查询给出的2,将它分成了ababa两段,前面的子串有a,b,ab,在后面分别出现了2,1,1次,所以答案是4。字符串长度是1000,而查询有1e5那么多,肯定要预处理ans数组的。总体思路为:
ac代码:
文章图片
文章图片
1 #include2 #include 3 using namespace std::tr1; 4 #define ll long long 5 #define maxn 1234 6 ll t,seed=131,ans[maxn]; 7 ll f[maxn],g[maxn],sum,x; //f【i】为前i个字母组成的前缀哈希成的数字 8 unordered_map pre,now; 9 char s[maxn]; 10 ll geth(int l,int r) 11 { 12return f[r]-f[l-1]*g[r-l+1]; 13 } 14 int main() 15 { 16scanf("%s%lld",s+1,&t); //输入字符串,从一开始 17int n=strlen(s+1); //长度为n 18g[0]=1; //....................... 19for(int i=1; i<=n; i++) 20{//................ 21g[i]=g[i-1]*seed; //g用于求子串的哈希值 22f[i]=f[i-1]*seed+s[i]; //将每个前缀哈希成一个数字(fi是ll) 23} 24for(int i=1; i<=n; i++) 25for(int j=i; j<=n; j++) 26pre[geth(i,j)]++; //i到j为一条子串,并将该子串哈希,放到pre里面,个数++ 27for(int i=1; i<=n; i++) 28{//从一开始设置断点 29for(int j=i; j>=1; j--) 30{ 31ll id=geth(j,i); //获得前件后缀的哈希值 32now[id]++; //当前后缀的个数++ 33if(pre[id])//若后件有该子串,sum+上该子串的个数 34sum+=pre[id]; 35}; 36for(int j=i; j<=n; j++) 37{ 38ll id=geth(i,j); //获取后件子串的哈希值 39pre[id]--; //子串个数-- 40if(now[id]) 41sum-=now[id]; 42} 43ans[i]=sum; //对此时的断点预处理完成大重点,sum没有初始化,是继续用的 44} 45while(t--) 46{ 47scanf("%lld",&x); 48printf("%lld\n",ans[x]); 49} 50return 0; 51 }
View Code
【字符串哈希&子串匹配】转载于:https://www.cnblogs.com/qq2210446939/p/10764810.html
推荐阅读
- JAVA(抽象类与接口的区别&重载与重写&内存泄漏)
- 宋仲基&宋慧乔(我们不公布恋情,我们直接结婚。)
- 一起来学习C语言的字符串转换函数
- 21天|21天|M&M《见识》04
- 字符串拼接成段落,换行符(\n)如何只执行n-1次
- 二叉树路径节点关键值和等于目标值(LeetCode--112&LeetCode--113)
- C语言的版本比较
- 2021—3—8日教练实践总结&呼吸练习&觉察日记
- JavaScript|JavaScript — call()和apply()、Date对象、Math、包装类、字符串的方法
- 奇迹-妖妈|奇迹-妖妈 感恩日记46/365&非暴力沟通第3天