首页 / 算法 / 哈希算法实现字符串匹配
哈希算法实现字符串匹配
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了哈希算法实现字符串匹配，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3858字，纯文字阅读大概需要6分钟。
内容图文
对于匹配字符串m和目标字符串n，最朴素的思想就是对于每个起始位置都o（m）地直接比较字符是否相同，最后时间复杂度为O（m*n）这样的时间复杂度在大多数时候都很不乐观，因此需要一些技巧降低时间复杂度。
哈希算法：
我们可以将一段字符串映射为数值然后比较数值大小，若相等则匹配成功。这是理想情况下的，要达到这样的效果需要哈希算法具备一定的抗碰撞性（即不同的字符串不会映射到同一数值）。在这个前提下，要是计算每个长度为m的字符串的哈希值，最终复杂度必然还是O（m*n），这里可以用滚动哈希的方法优化。
对于匹配字符串 s=C?C?C?.....C? 哈希值H=C?*B^(m-1)+C?*B^(m-2)+C?*B^(m-3)+...+C? 其中B取一个非常大素数如（1e9+7），B^(m-1)表示B的m-1次方
对于目标字符串ss=A?A?A?....A? 已知A?开始长度为m的字符串的哈希值为h ， 要得到A?开始长度为m的字符串的哈希值只需
h′ = h*B-A?*B^m+D 其中D为第（m+1）位字符， 就可以在O（n）的时间复杂度内实现字符串匹配
先上代码：
1 #include<iostream>
2 #include<algorithm>
3 #include<string>
4 #include<set>
5 #include<vector>
6 #include<queue>
7 #include<stack>
8 #include<map>
9 #include<cmath>
10 #include<string>
11 using namespace std;
12 typedef unsigned long long ull;
13 char s[1010][1010];
14 char pat[110][55][1010];
15 ull hash_[1010][1010], temp[1010][1010];
16 const ull B = 1e9 + 7, A = 9973;
17 int N, M, P, Q, T;
18 void comput_hash(char a[][1010], int n, int m)
19 {
20 int i, j, k;
21 ull e = 0, t1 = 1, t2 = 1;
22 for (i = 1; i <= Q; i++)
23 t1 *= A;
24 for (i = 1; i <= n; i++)
25 {
26 e = 0;
27 for (j = 1; j <= Q; j++)
28 e = e * A + a[i][j];
29 for (j = 1; j + Q - 1 <= m; j++)
30 {
31 temp[i][j] = e;
32 if (j + Q <= m)
33 e = e * A - a[i][j] * t1 + a[i][j + Q];
34 }
35 }
36
37 e = 0;
38 for (i = 1; i <= P; i++)
39 t2 *= B;
40 for (j = 1; j + Q - 1 <= m; j++)
41 {
42 e = 0;
43 for (i = 1; i <= P; i++)
44 e = e * B + temp[i][j];
45 for (i = 1; i + P - 1 <= n; i++)
46 {
47 hash_[i][j] = e;
48 if (i + P <= n)
49 e = e * B - temp[i][j] * t2 + temp[i + P][j];
50 }
51 }
52 }
53 int main()
54 {
55 int i, j, k;
56 int cnt = 0, ans;
57 while (~scanf("%d%d%d%d%d", &N, &M, &T, &P, &Q))
58 {
59 if (N == 0 && M == 0 && P == 0 && Q == 0 && T == 0)
60 break;
61 for (i = 1; i <= N; i++)
62 scanf("%s", s[i] + 1);
63 for (k = 1; k <= T; k++)
64 for (i = 1; i <= P; i++)
65 scanf("%s", pat[k][i] + 1);
66
67 multiset<ull>ml;
68 for (i = 1; i <= T; i++)
69 {
70 comput_hash(pat[i], P, Q);
71 ml.insert(hash_[1][1]);
72 }
73
74 comput_hash(s, N, M);
75 for (i = 1; i + P - 1 <= N; i++)
76 for (j = 1; j + Q - 1 <= M; j++)
77 ml.erase(hash_[i][j]);
78
79 ans = T - ml.size();
80 printf("Case %d: %d\n", ++cnt, ans);
81 }
82 return 0;
83 }
对于这道题，我们可以先只看一个维度，对于一个维度的匹配就是简单的板子题，就像之前所说进行匹配即可，在拓展到二维时，应该考虑行列均相同。
按一个维度的思想，我们要保证一个字符相同，然后是一段字符相同。
这里我们可以将每一行的一段字符串的哈希值视为“一个字符”’（哈希算法需要足够抗碰撞允许我们这么做）
然后我们继续在列方向上进行匹配即可。
在代码中 用unsigned long long 来存哈希值能让数据自然溢出，若不用ull，则应在数据溢出前模上一个足够大的素数，
以B=1e9+7 作为行的基数 A=9973作为列的基数
先计算每个匹配模式的hash值，放入multiset里，hash[ i ][ j ]表示以从 i 到 i+P ，j 到 j+Q的匹配模式的哈希值
再计算匹配对象的，然后将匹配对象中出现过的hash值从multiset里剔除，
此时在multiset里剩下的就是未在匹配对象出现过的匹配模式的个数
那么答案就是用匹配模式的个数 T 减去multiset里元素个数
参考书籍————《挑战程序设计竞赛》
内容总结
以上是互联网集市为您收集整理的哈希算法实现字符串匹配全部内容，希望文章能够帮你解决哈希算法实现字符串匹配所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。