KMP算法，kmp算法詳解
1 /* next數組是KMP算法的關鍵，next數組的作用是：當模式串T和主串S失配
2 * ，next數組對應的元素指導應該用T串中的哪一個元素進行下一輪的匹配
3 * next數組和T串相關，和S串無關。KMP的關鍵是next數組的求法。
4 *
5 * ———————————————————————————————————————————————————————————————————
6 * | T | 9 | a | b | a | b | a | a | a | b | a |
7 * ————————————————————————————————————————————————————————————————————
8 * |index| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
9 * ————————————————————————————————————————————————————————————————————
10 * |next | X | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | * ————————————————————————————————————————————————————————————————————
11 *
12 step 0:
13 * j = 0; i = 1; next[1] = 0
14 * | 1 2 3 4 5 6 7 8 9 10
15 * —————————————————————————————————————————————————————————————————————
16 * i = | 1
17 * j = | 0
18 *
19 step 1:
20 * j == 0;-->i = 2;j = 1;next[2] = 1;
21 * | 1 2 3 4 5 6 7 8 9 10
22 * —————————————————————————————————————————————————————————————————————
23 * i = | 1 2
24 * j = | 0 1
25 *
26 step 2:
27 * T[2] != T[1];--> j = next[1]-->j = 0;i = 2
28 * | 1 2 3 4 5 6 7 8 9 10
29 * —————————————————————————————————————————————————————————————————————
30 * i = | 1 2 2
31 * j = | 0 1 0
32 *
33 step 3:
34 * j == 0 --> j++;i++;--> j = 1;i = 3;next[3] = 1
35 * | 1 2 3 4 5 6 7 8 9 10
36 * —————————————————————————————————————————————————————————————————————
37 * i = | 1 2 2 3
38 * j = | 0 1 0 1
39 *
40 step 4:
41 * T[3] == T[1];-->i++;j++;-->i=4,j=2; next[4] = 2
42 * | 1 2 3 4 5 6 7 8 9 10
43 * —————————————————————————————————————————————————————————————————————
44 * i = | 1 2 2 3 4
45 * j = | 0 1 0 1 2
46 *
47 step 5:
48 * T[4] == T[2];-->i++;j++-->i=5,j=3-->next[5]=3
49 * | 1 2 3 4 5 6 7 8 9 10
50 * —————————————————————————————————————————————————————————————————————
51 * i = | 1 2 2 3 4 5
52 * j = | 0 1 0 1 2 3
53 *
54 step 6:
55 * T[5] == T[3];-->i++,j++;-->i=6,j=4;next[6]=4;
56 * | 1 2 3 4 5 6 7 8 9 10
57 * —————————————————————————————————————————————————————————————————————
58 * i = | 1 2 2 3 4 5 6
59 * j = | 0 1 0 1 2 3 4
60 *
61 step 7:
62 * T[6] != T[4];-->j = next[j];-->j=2;
63 * | 1 2 3 4 5 6 7 8 9 10
64 * —————————————————————————————————————————————————————————————————————
65 * i = | 1 2 2 3 4 5 6 6
66 * j = | 0 1 0 1 2 3 4 2
67 *
68 step 8:
69 * T[2] != T[6];-->j = next[j];-->j = 1;
70 * | 1 2 3 4 5 6 7 8 9 10
71 * —————————————————————————————————————————————————————————————————————
72 * i = | 1 2 2 3 4 5 6 6 6
73 * j = | 0 1 0 1 2 3 4 2 1
74 *
75 step 9:
76 * T[1] == T[6];-->i++,j++;-->i=7,j=2;next[7]=2;
77 * | 1 2 3 4 5 6 7 8 9 10
78 * —————————————————————————————————————————————————————————————————————
79 * i = | 1 2 2 3 4 5 6 6 6 7
80 * j = | 0 1 0 1 2 3 4 2 1 2
81 *
82 step 10:
83 * T[2]!=[7];-->j=next[j];-->j=1;
84 * | 1 2 3 4 5 6 7 8 9 10 11
85 * ———————————————————————————————————————————————————————————————————————————————————
86 * i = | 1 2 2 3 4 5 6 6 6 7 7
87 * j = | 0 1 0 1 2 3 4 2 1 2 1
88 *
89 step 11:
90 * T[1]==T[7];-->i++,j++;-->i=8,j=2;-->next[8]=2;
91 * | 1 2 3 4 5 6 7 8 9 10 11 12
92 * ———————————————————————————————————————————————————————————————————————————————————
93 * i = | 1 2 2 3 4 5 6 6 6 7 7 8
94 * j = | 0 1 0 1 2 3 4 2 1 2 1 2
95 *
96 step 12:
97 * T[2]==T[8];-->i++,j++;-->i=9,j=3;next[9]=3;
98 * | 1 2 3 4 5 6 7 8 9 10 11 12
99 * ———————————————————————————————————————————————————————————————————————————————————
100 * i = | 1 2 2 3 4 5 6 6 6 7 7 8
101 * j = | 0 1 0 1 2 3 4 2 1 2 1 2
102 * */
103
104
105 /* 模式串：ababaadacc
106 * 前綴和後綴的概念：
107 * 前綴：除去最後一個元素之外的所有包含第一個元素的連續字符串
108 * 對於模式串中的d則前綴有：a ab aba abab ababa
109 * 後綴：除去第一個元素之外的所有的包含最後一個元素的連續字符串
110 * 對於模式串中的d則前綴有：a aa baa abaa babaa
111 * */
112
113 #include<stdio.h>
114
115 //next數組的作用： 當模式串匹配失敗的時候，next數組的相對應的元素指示
116 // 要從模式串的哪個位置開始和當前的主串的失配的元素開
117 // 始進行下一輪的匹配。
118
119
120 void getNext(char* T, int* next){
121 int i = 1; //i的值是將要計算的next的下標
122 int j = 0; //前綴
123 next[1] = 0;
124 while( i <= 9 ){
125 if( 0 == j || T[i] == T[j] ){
126 //T[i] == T[j]則向後匹配
127 //當前的next[i]的值已經確定為j
128 //j==0或為初始，或者是沒有匹配的前綴
129 //此時i和j自加
130 i++;
131 j++;
132 next[i] = j;
133 }
134 else{
135 j = next[j]; //next的作用：當T[j]和T[i]失配，next[j]的值
136 //指示的下一次要進行匹配的位置，有點像遞歸。
137 }
138 }
139 }
140 int KMP(char* S, char* T, int startPosition){
141 int i = startPosition;
142 int j = 1;
143 int next[30];
144 getNext(T,next);
145 while( i <= 17 && j <= 9 ){ //j>則說明匹配成功了，i>則說明失敗了
146 if( j == 0 || S[i] == T[j] ){ //j==0;可以理解為要重新開始
147 i++;
148 j++;
149 }
150 else{
151 j = next[j];
152 }
153 }
154 if( j > 9 ){
155 return i - 9;
156 }
157 else
158 return 0;
159 }
160
161
162 int main(){
163 char S[20] = " absfeafdababaaaba";
164 char T[20] = " ababaaaba";
165 int result;
166 result = KMP(S,T,1);
167 printf("the position is %d\n",result);
168 return 0;
169 }
