http://poj.org/problem?id=3461
类似题目:LeetCode 30. 串联所有单词的子串(字符串哈希)
模式串在主串中出现过几次。
#include <stdio.h>
#include <iostream>
#include <cstring>
int next[10001];
char a[1000001], b[10001];
void calNexts(char *b, int m, int *next)
{
next[0] = -1;
int j = 0, k = -1;
while(j < m)
{
if(k == -1 || b[j] == b[k])
{
j++;k++;
next[j] = k;
}
else
k = next[k];
}
}
int str_kmp(char *a, int n, char *b, int m)
{
calNexts(b, m, next);
int i = 0, j = 0, times = 0;
while(i < n && j < m)
{
if(j == -1 || a[i] == b[j])
{
i++;j++;
}
else
{
j = next[j];
}
if(j == m)
{
times++;
j = next[j];
}
}
return times;
}
int main()
{
int count;
std::cin >> count;
while(count--)
{
scanf("%s",&b);
scanf("%s",&a);
printf("%d\n",str_kmp(&a[0], strlen(a), &b[0], strlen(b)));
}
return 0;
}
参考别人的哈希函数,哈希值的求法很犀利
自己推导的过程如下:
/**
* @description: poj 3461 字符串匹配,哈希法
* @author: michael ming
* @date: 2019/6/26 21:59
* @modified by:
*/
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <cmath>
#define K 25 //K大于等于字符集数 k>=25
typedef unsigned long long ull;
char a[1000001], b[10001];
ull ha[1000001];
ull powk[10001];//存储K的幂值
using namespace std;
void fillpowk(int m)
{
powk[0] = 1;
for(int i = 1; i <= m; ++i)
powk[i] = powk[i-1]*K;
}
ull hashf(int m, char *str)
{
ull value = 0;
for(int i = 0; i < m; ++i)
value = value * K + str[i];
return value;
}
int str_RK(char *a, int n, char *b, int m)//a是主串,b是模式串
{
fillpowk(m);
int i, times = 0;
ull hash_val, value = 0;
value = hashf(m,b); //计算模式串的hash值value
ha[0] = ull(a[0]);
for(i = 1; i < n; ++i)
ha[i] = ha[i-1] * K + a[i];
for(i = 0; i < n-m+1; ++i)//最多n-m+1次比较
{
if(i == 0)
hash_val = hashf(m,a);
else
hash_val = ha[i+m-1] - ha[i-1]*powk[m];
//这个公式可以自己推导一下
if(hash_val == value)
{//如果子串哈希值等于模式串的,匹配成功(该哈希无冲突)
times++;
}
}
return times;
}
int main()
{
int count;
std::cin >> count;
while(count--)
{
scanf("%s",&b);
scanf("%s",&a);
printf("%d\n",str_RK(&a[0], strlen(a), &b[0], strlen(b)));
}
return 0;
}