这两天又看了一遍《算法导论》上面的字符串匹配那一节，下面是实现的几个程序，可能有错误，仅供参考和交流。

关于详细的讲解，网上有很多，大多数算法及数据结构书中都应该有涉及，由于时间限制，在这就不重复了。

需要说明的是：

　stra：主串，及需要从中寻找模式串的字符串

　strb：模式串

　《算法导论》上面包括严蔚敏老师《数据结构》，字符串下表是按从1开始，并且《数据结构》一书中貌似吧字符串的第一个字符用来储存字符串长度。这里我改成了0。

　maxlen ：字符串的最长长度

1. 朴素算法 （最容易理解的，时间复杂度有点高 预处理时间：O（0），查询时间：O（（n-m-1） * m））

/**字符串模式匹配的朴素算法s为偏移量*/#include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxlen = 1000;void NAIVE_STRING_MATCHER(char* stra, char* strb){    int n(strlen(stra)), m(strlen(strb));    for (int s(0);s <= n - m; ++s)        if (stra[s] == strb[0])        {            bool flag = true;            for (int i(0); i < m; ++i)                if (stra[s+i] != strb[i])                {                    flag = false;                    break;                }            if (flag)            {                cout<<"Pattern occurs with shifts "<
        <
         
          >stra && cin>>strb)        NAIVE_STRING_MATCHER(stra, strb);    return 0;}
         
       
      
     

　　

　　2. Rabin & Karp 算法 （这个算法让我想起了哈希表 预处理时间：O（m），查询时间：O（（n-m-1） * m）, 哈哈, 不比朴素算法快，因为看了，写了，就贴出来了，可以不看）

/**Rabin, Karp 发现的字符串匹配算法*/#include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxlen = 10000;int d(10), mod(100000007);void RABIN_KARP_MATCHER(char* stra, char* strb){    int n(strlen(stra)), m(strlen(strb)), p(0), t(0), h(1);    //preprocessing    for (int i(0); i < m-1; ++i)        h = i ? h * d % mod : d % mod;    for (int i(0); i < m; ++i)    {        p = (d * p + strb[i]) % mod;        t = (d * t + stra[i]) % mod;    }    for (int s(0); s <= n - m; ++s)    {        if (p == t)        {            bool flag = true;            for (int j(0); j < m; ++j)                if (stra[s+j] != strb[j])                {                    flag = false;                    break;                }            if (flag)            {                cout<<"Pattern occurs with shifts "<
        <
         
          >stra && cin>>strb)        RABIN_KARP_MATCHER(stra, strb);    return 0;}
         
       
      
     

　　3.《算法导论》还给了有限自动机的算法，处理时间要比KMP算法长，查询时间复杂度一样，可以说，KMP是对有限自动机预处理优化之后的算法。下面是

KMP算法   预处理时间：O（m），查询时间：O（n）

　　事先说明：算法是《算法导论》思路，但是却用了严蔚敏老师《数据结构》中的一些变量，比如next数组，本以为其和《算法导论》中的 pi （圆周率的符号，在这用了拼音） 数组一样，现在看来有一点不一样。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int maxlen = 10000;void get_next(char* strb, int* next){	int i(1), j(-1), d(strlen(strb));	next[0] = -1;	for (; i < d; ++i)	{		while(j >= 0 && strb[j+1] != strb[i])			j = next[j];		if (strb[j+1] == strb[i])			j += 1;		next[i] = j;	}}void KMP_MATCHER(char* stra, char* strb){	int n(strlen(stra)), m(strlen(strb)), next[maxlen];	get_next(strb, next);	int i(0), j(-1);	for (int i(0); i < n; ++i)	{		while(j >= 0 && strb[j+1] != stra[i])			j = next[j];		if (strb[j+1] == stra[i])			j += 1;		if (j == m - 1)		{			cout<<"Pattern occurs with shifts "<
         >stra && cin>>strb)		KMP_MATCHER(stra, strb);	return 0;}
        
       
      
     

　　再次重申：代码可能有错，欢迎大家指正。