# 简单的模式匹配算法

，并且 `m`为主串， `n`为模式串。

``````
# use type hint to get a smart hint
def index(target: str, pattern: str) -> int:
# 这一波使用普通的算法，即i回退
i = 0
j = 0
len_i = len(target)
len_j = len(pattern)
while (i<= len_i-1) and (j<=len_j-1):
if target[i] == pattern[j]:
i += 1
j += 1
else:
# 回退
i = i - j + 1
print ("i value: %d"%i)
j = 0
print("j is %d"%j)
if (j > len_j-1):
return i - len_j
else:
return -1

print(index("abc", "abc"))
print(index("aabc", "abc"))
``````

# 改进的模式匹配算法——KMP算法

KMP算法全称为克努特—莫里斯—普拉特操作，此算法时间复杂度为：

KMP算法时间复杂度
,其与之前算法最大的不同在于：指针 `i`不回退，而是移动模式串。因此，算法的关键部分在于，在匹配不成功的时候，我们该如何移动模式串呢，又该移动多少位的模式串呢？

Python代码如下：

``````def get_next(pattern:str) ->list:
# 求失效函数值序列
length = len(pattern)
next = [None]*length
next[0] = -1  # 失效序列初始值设置为-1（某些国内教材设定为0）
i = 0
j = -1  # represents the value of next[]
while (i < length-1):
# mmp C/C++写多了，括号习惯了
if (j == -1 or pattern[i] == pattern[j]):
# j == -1 means this is the first value, need process specially
i += 1
j += 1
next[i] = j
else:
j = next[j]
return next
``````

``````def get_nextval(pattern:str) ->list:
# 改进的失效函数序列值算法
length = len(pattern)
next = [None]*length
next[0] = -1  # 失效序列初始值设置为-1（某些国内教材设定为0）
i = 0
j = -1  # represents the value of next[]
while (i < length-1):
if (j == -1 or pattern[i] == pattern[j]):
# j == -1 means this is the first value, need process specially
i += 1
j += 1
if pattern[i] == pattern[j]:
next[i] = next[j]
else:
next[i] = j
else:
j = next[j]
return next
``````

``````if pattern[i] == pattern[j]:
next[i] = next[j]
else:
next[i] = j
``````

## KMP算法

``````def kmp(target:str, pattern:str) -> int:
# kmp(非改进)算法，模式匹配
next = get_next(pattern)  # 得到失效值序列
i = 0
j = 0
len_i = len(target)
len_j = len(pattern)
while i<=len_i-1 and j <=len_j-1 :
if target[i] == pattern[j] or j == -1:
i += 1
j += 1
else:
j = next[j]
# if j == -1:
#     i += 1
#     j += 1

if j >= len_j-1:
return i-len_j
else:
return -1
``````

# C语言实现过程

``````/*
written at 2018-5-28 19:27:42
KMP算法中计算next的实现方式
*/
#include
#include

void next1(char *s, int *next){
// s为字符串，next为失效函数序列
int length = strlen(s);  // 字符串的长度
int i = 0; int j = -1;
next[0] = -1;
while (i < length-1){
if (j==-1 || s[i] == s[j]){i++; j++;next[i] = j;}
else{j = next[j];}
}
}

void next_val(char *s, int *next){
// 改进版本的失效函数
int length = strlen(s);
int i = 0; int j = -1;
next[0] = -1;
while (i= length_pat) return i - length_pat;
else return 0;  // pat fail
}

void main(){
char *s = "peng jidong";
char *pat = "jidong";
int ans = kmp(s, pat, 1);
printf("ans is %d\n", ans);
// printf the answer to examine it right or not
for (int i=ans; i``````
``` ```
``` ```
``` ```
``` ```
``` ```
``` ```
``` ```
``` ```
``` 你可能感兴趣的 HttpClient 4.3与4.3版本以下版本比较 spjich javahttpclient Essential Studio Enterprise Edition 2015 v1新功能体验 Axiba .net [宇宙与天文]微波背景辐射值与地球温度 comsci 背景 lvs-server 男人50 server java的WebCollector爬虫框架 oloz 爬虫 jQuery append 与 after 的区别 小猪猪08 mysql知识充电 香水浓 mysql 我的架构经验系列文章索引 agevs 架构 按字母分类： ABCDEFGHIJKLMNOPQRSTUVWXYZ其他 首页 - 关于我们 - 站内搜索 - Sitemap - 侵权投诉 版权所有 IT知识库 CopyRight © 2000-2050 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号 ```