图 1 串的第一次模式匹配示意图
图 2 串的第二次模式匹配示意图
图 3 串的第三次模式匹配示意图
图 4 串模式匹配成功示意图
#include <stdio.h>
#include <string.h>
//串普通模式匹配算法的实现函数，其中 B是伪主串，A是伪子串
int mate(char * B,char *A){
int i=0,j=0;
while (i<strlen(B) && j<strlen(A)) {
if (B[i]==A[j]) {
i++;
j++;
}else{
i=i-j+1;
j=0;
}
}
//跳出循环有两种可能，i=strlen(B)说明已经遍历完主串，匹配失败；j=strlen(A),说明子串遍历完成，在主串中成功匹配
if (j==strlen(A)) {
return i-strlen(A)+1;
}
//运行到此，为i==strlen(B)的情况
return 0;
}
int main() {
int number=mate("ababcabcacbab", "abcac");
printf("%d",number);
return 0;
}
程序运行结果：
6
注意，在实现过程中，我们借助 i-strlen(A)+1 就可以得到成功模式匹配所用的次数，也就是串 A 移动的总次数。O(n)，n 表示串 A 的长度，即第一次匹配就成功。O(n*m)，n 为串 A 的长度，m 为串 B 的长度。例如，串 B 为 "0000000001"，而串 A 为 "01"，这种情况下，两个串每次匹配，都必须匹配至串 A 的最末尾才能判断匹配失败，因此运行了 n*m 次。
本文链接：http://task.lmcjl.com/news/16298.html