# 几种常见的字符串匹配算法

#1. 朴素算法

``````#include<stdio.h>
#include<string.h>
void search(char *pat, char *txt)
{
int M = strlen(pat);
int N = strlen(txt);

/* A loop to slide pat[] one by one */
for (int i = 0; i <= N - M; i++)
{
int j;

/* For current index i, check for pattern match */
for (j = 0; j < M; j++)
{
if (txt[i+j] != pat[j])
break;
}
if (j == M)  // if pat[0...M-1] = txt[i, i+1, ...i+M-1]
{
printf("Pattern found at index %d \n", i);
}
}
}

/* Driver program to test above function */
int main()
{
char *pat = "AABA";
search(pat, txt);
getchar();
return 0;
}
``````

#2. Rabin-Karp算法

Rabin-Karp算法的思想：

1. 假设子串的长度为M,目标字符串的长度为N
2. 计算子串的hash值
3. 计算目标字符串中每个长度为M的子串的hash值（共需要计算N-M+1次）
4. 比较hash值
5. 如果hash值不同，字符串必然不匹配，如果hash值相同，还需要使用朴素算法再次判断

``````/* Following program is a C implementation of the Rabin Karp Algorithm
given in the CLRS book */

#include<stdio.h>
#include<string.h>

// d is the number of characters in input alphabet
#define d 256

/*  pat  -> pattern
txt  -> text
q    -> A prime number
*/
void search(char *pat, char *txt, int q)
{
int M = strlen(pat);
int N = strlen(txt);
int i, j;
int p = 0;  // hash value for pattern
int t = 0; // hash value for txt
int h = 1;

// The value of h would be "pow(d, M-1)%q"
for (i = 0; i < M-1; i++)
h = (h*d)%q;

// Calculate the hash value of pattern and first window of text
for (i = 0; i < M; i++)
{
p = (d*p + pat[i])%q;
t = (d*t + txt[i])%q;
}

// Slide the pattern over text one by one
for (i = 0; i <= N - M; i++)
{

// Chaeck the hash values of current window of text and pattern
// If the hash values match then only check for characters on by one
if ( p == t )
{
/* Check for characters one by one */
for (j = 0; j < M; j++)
{
if (txt[i+j] != pat[j])
break;
}
if (j == M)  // if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1]
{
printf("Pattern found at index %d \n", i);
}
}

// Calulate hash value for next window of text: Remove leading digit,
if ( i < N-M )
{
t = (d*(t - txt[i]*h) + txt[i+M])%q;

// We might get negative value of t, converting it to positive
if(t < 0)
t = (t + q);
}
}
}

/* Driver program to test above function */
int main()
{
char *txt = "GEEKS FOR GEEKS";
char *pat = "GEEK";
int q = 101;  // A prime number
search(pat, txt, q);
getchar();
return 0;
}
``````

#3. KMP算法

KMP算法是一个比较难以理解的算法。国内非顶尖的大学数据结构大都使用的是清华严老师的 《数据结构》，这本书在第四章讲到了KMP算法，我认真看了两遍没有看懂。到现在我终于明白 了以后，我想说，真的是严老师实在讲得太烂了。

KMP算法要讲清楚很不容易，网络上一搜一大堆材料，看完还是似懂非懂。我不准备再讲一遍， 我也不相信自己会讲得比网络上大多数文章讲得好，在此给大家推荐阮一峰老师的《字符串匹配的KMP算法》。

1. KMP算法的思想就是，当子串与目标字符串不匹配时，其实你已经知道了前面已经匹配成功那 一部分的字符（包括子串与目标字符串）。以阮一峰的文章为例，当空格与D不匹配时，你其实 知道前面六个字符是”ABCDAB”。KMP算法的想法是，设法利用这个已知信息，不要把”搜索位置” 移回已经比较过的位置，继续把它向后移，这样就提高了效率

2. 部分匹配表是模式自己与自己的匹配

#4. Boyer-Moore算法

#5. Sunday算法

http://blog.163.com/yangfan876@126/blog/static/80612456201342205056344

/
Published under (CC) BY-NC-SA in categories 算法  tagged with KMP  BM  算法  字符串匹配