kmp算法

KMP模式匹配算法

（1）失配函数

（2）模式匹配算法

模式匹配算法：主串不回退，从串回退。（相当于从串不断地移动，）

设主串为s1 s2s3s4......sn-1sn

从串为p1p2.....pj

模式匹配思路：

对于任意匹配;

假设在si处匹配

主串：　　s1s2s3s3.....si-j......si-1si。。。

模式串： p0.....pj-1pj。。。

假设在主串的 i 处，模式串的 j 处发生失配，si!=pj

若j=0，则主串直接移动一个从串重新开始比较。

若j!=0,则需要求从串的第 j-1 个元素的失配函数值+1开始比较

失配函数：

定义1：令p=p0p1...pn-1是个模式，则其失配函数的定义为：

f(j)= i为满足i<j且使得p0p1..pi=pj-ipj-i+1.....pj的最大整数　　　　i>=0

f(j)=-1　　　　　　　　　　　　　　　　　　　　　　　　　　　其他情况

如p=abcabcacab的失配函数为

j　　0　　1　　2　　3　　4　　5　　6　　7　　8　　9

p　　a　　b　　c　　a　　b　　c　　a　　c　　a　　b

f(j)　-1　　-1　-1　　0　　1　　2　　3　　-1　　0　　1

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define max_string_size  100
 4 #define max_pattern_size 100
 5 
 6 int failure[max_pattern_size];
 7 char string[max_string_size];
 8 char pat[max_pattern_size];
 9 
10 int pmatch(char *string,char *pat);
11 void fail(char * pat);
12 int main()
13 {
14     
15     return 0;
16  } 
17 
18 int pmath(char *string ,char *pat)
19 {
20     int i=0,j=0;
21     int lens=strlen(string);        //主串的长度 
22     int lenp=strlen(pat);            //模式串的长度 
23     
24     while( i < lens && j < lenp){
25         if(string[i] == pat[j]){        //当一一相等时往下比较 
26             i++;
27             j++; 
28         } 
29         //失配 
30         else if(j == 0){    //如果是第一个字符失配，直接主串加一继续从新比较        
31             i++; 
32         }
33         //如果不是第一个字符失配，找出f(j-1)的下一个比较，f(j-1)是失配函数的值    
34         else                            
35             j=failure[j-1]+1;
36     }
37     
38     return ((j==lenp)?(i-lenp):-1);//匹配完成返回匹配串的第一个字符索引值，否则返回-1 
39     
40 }
41 /*
42 1.f(j)=-1  j=0
43 2.f(j)=f^m(j-1)+1   m满足f^k(j-1)+1=j的最小整数k
44 3.f(j)=-1          如果没有满足 2的全为-1 
45 
46 */
47 void fail(char * pat)
48 {
49     int n=strlen(pat);
50     int j;
51     int i;
52     failure[0]=-1;        //j = 0 直接为0 
53     
54     for(j = 1; j < n; j++){
55         i=failure[j-1];        //p->(f(j))=p->(f(j-1)+1)是否相等 
56         while((pat[j] != pat[i+1]) && i >= 0) //有递归 
57             i=failure[i];
58         if(pat[j]==pat[i+1])    //相等直接就是f(j)=f(j-1)+1 
59             failure[j]=i+1;
60         else                    //其他情况f(j)=-1 
61              failure[j]=-1;
62     }
63  }