基于C#实现KMP算法

next[j] =  -1     当 j=0 时
next[j] =  max{k| 0

• 1
• 2
• 3

好，接下来的问题就是如何求出 next[j],这个也就是 kmp 思想的核心，对于 next[j]的求法，我们采用递推法，现在我们知道了 next[j]=k，我们来求 next[j+1]=？的问题，其实也就是两种情况：
①：Pk=Pj 时 则 P0P1…Pk=Pj-kPj-k+1…Pj, 则我们知：

next[j+1]=k+1。
1

又因为 next[j]=k，则

next[j+1]=next[j]+1。
1

②：Pk!=Pj 时 则 P0P1…Pk!=Pj-kPj-k+1…Pj,其实这里我们又将模式串的匹配问题转化为了上面我们提到的”主串“和”模式串“中寻找 next 的问题，你可以理解成在模式串的前缀串和后缀串中寻找 next[j]的问题。现在我们的思路就是一定要找到这个 k2，使得 Pk2=Pj，然后将 k2 代入 ① 就可以了。
设 k2=next[k]。 则有 P0P1…Pk2-1=Pj-k2Pj-k2+1…Pj-1。
若 Pj=Pk2， 则 next[j+1]=k2+1=next[k]+1。
若 Pj!=Pk2, 则可以继续像上面递归的使用 next，直到不存在 k2 为止。
好，下面我们上代码。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SupportCenter.Test
{
  public class Program
  {
     static void Main(string[] args)
     {
         string zstr = "ababcabababdc";

         string mstr = "babdc";

         var index = KMP(zstr, mstr);

         if (index == -1)
             Console.WriteLine("没有匹配的字符串！");
         else
             Console.WriteLine("哈哈，找到字符啦，位置为：" + index);

         Console.Read();
     }

     static int KMP(string bigstr, string smallstr)
     {
         int i = 0;
         int j = 0;

         //计算“前缀串”和“后缀串“的next
         int[] next = GetNextVal(smallstr);

         while (i < bigstr.Length && j < smallstr.Length)
         {
             if (j == -1 || bigstr[i] == smallstr[j])
             {
                 i++;
                 j++;
             }
             else
             {
                 j = next[j];
             }
         }

         if (j == smallstr.Length)
             return i - smallstr.Length;

         return -1;
     }

     /// 

     /// p0,p1....pk-1         （前缀串）
     /// pj-k,pj-k+1....pj-1   （后缀串)
     /// 
     /// 
     /// 
     static int[] GetNextVal(string smallstr)
     {
         //前缀串起始位置("-1"是方便计算）
         int k = -1;

         //后缀串起始位置（"-1"是方便计算）
         int j = 0;

         int[] next = new int[smallstr.Length];

         //根据公式： j=0时，next[j]=-1
         next[j] = -1;

         while (j < smallstr.Length - 1)
         {
             if (k == -1 || smallstr[k] == smallstr[j])
             {
                 //pk=pj的情况: next[j+1]=k+1 => next[j+1]=next[j]+1
                 next[++j] = ++k;
             }
             else
             {
                 //pk != pj 的情况:我们递推 k=next[k];
                 //要么找到，要么k=-1中止
                 k = next[k];
             }
         }

         return next;
     }
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90