第一次写博客，不足之处还请大家指教。下面直接进入主题。
概述
字符串匹配相信大家都很熟悉，有很多种解法。比如kmp算法啊，PabinKarp算法啊，当然暴力解法也都行。
前几天看蓝桥《算法很美》的视频，里面讲到了PabinKarp算法，觉得挺好玩儿的今天我们就来浅谈一下PabinKarp算法，对自己来说也算个总结。
PabinKarp算法其实就是预处理吧。首先用类似于求进制的方法对模式串进行求值，如选一个进制数(31进制)算出它的hash值。然后对原字符串进行处理，具体的处理方法就是。从原字符串的第一个字符开始到模式串的位数，把它看成一个字符串算出它的hash值，然后和模式串的hash值进行比较，相等的话就表示这个字符串与模式串相同。之后再从第二字符开始到模式串的位数，算出这个字符串的hash值再与模式串的hash值进行比较，以此类推直至比较完整个字符串。我写的这个话是我个人对PabinKarp算法理解的一个白话，可能有小伙伴不怎么理解，举个具体例子把。
实例
原串为:abababa
模式串为:aba
首先选一个进制数就31吧，然后用求进制的方法将模式串转换成一个hash值。之后就是对原串的处理了。因为模式串大小是3,所以就从原串的第一个字符开始到第三个字符结束，也就是aba。然后同样用转模式串的方法对这个字串进行运算，算出它的hash值。把这个hash值与模式串的hash值进行比较，相等就表示这个字串与模式串相等，反之就是不等。然后再从第二个字符开始，把它看成是第一位直到第三位结束，也就是bab，算出它的hash值与模式串比较，看是否相等，之后就是从第三、第四位开始以此类推。直到原串的第六位结束，因为你从第六位开始划分，你划不出来三个，它后面只有一个字符。换句话说当你比完第从五位字符开始划分的那个字串后，你就要结束你的循环了，不能再继续下去了。我举得这个例子后，大家应该就对什么是PabinKarp算法有个大致的了解把。从写程序的方面来看，我们大致可以理解为我们要完成三件事，第一:求出模式串的hash值，第二:构建hash数组里面存放从原串的第一个字符开始到第五个字符结束的这些个字串的hash值。第三:将模式串的hash值与hash数组里面的值比较，找出相等的字串。下面我们就直接来看代码
代码
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <string.h>
#define Seed 31//选的k进制数
char *fun1(char *string,int left,int right);//截断字符串的方法
int fun2(char *s); //求字符串hash值的方法
int *fun(char *s,int n);//构建hash数组的方法
void match1(char *s,char *ss);//传入原串和模式串，然后依次调用函数
void match(int hash_p,int hash_s[]);//比较模式串的hash值与hash数组的值，并输出相等字串的第一个字符的下标
static count=0;//定义一个全局变量，表示hash数组的大小
int main(void) {
char *n=”abababa”;
char *m=”aba”;
match1(n,m);
return 0;
}
void match1(char *s,char *ss)
{
int hash_p=fun2(ss);
match(hash_p,fun(s,strlen(ss)));
}
void match(int hash_p,int hash_s[])
{
int i;
for(i=0;i<=count;i++)
{
if(hash_p==hash_s[i])
{
printf(“下标为：%d\n”,i);
}
}
}
//构建hash数组
int *fun(char s,int n)
{
int String;
int m=(strlen(s)-n+1);
String=(int)malloc(m sizeof(int));
if(NULL == String)
{
printf(“内存溢出. \n”);
exit(0);
}
count=strlen(s)-n+1;
String[0]=fun2(fun1(s,0,n));
int i;
int v;
for(i=n;i<strlen(s);i++)
{
int newChar=s[i];
int oChar=s[i-n];
v=(int)(String[i-n]*Seed+newChar-pow(Seed,n)*oChar)%INT_MAX;
count++;
String[i-n+1]=v;
}
return String;
}
int fun2(char s)//求字符串的hash值
{
int hash=0;
int i;
for(i=0;i<strlen(s);i++)
{
hash=Seedhash+(int)s[i];
}
return hash%INT_MAX;
}
char *fun1(char *string,int left,int right)//截子符串
{
char sc;
int string_length=strlen(string);
int real_length=((string_length-left)>=right?right:(string_length-left));
if (NULL == (sc=(char) malloc(real_length * sizeof(char))))
{
printf(“Memory overflow . \n”);
exit(0);
}
strncpy(sc,string+left,real_length);
sc[real_length]=’\0’;
return sc;