4.2

模式匹配概念

从主串找到模式串中相同的子串，并返回所在位置

朴素模式匹配

发现不同就检查子串

int Index(SString S,SString T){ int k = 1; int i = k,j=k; while(i<=S.length && j<=T.length){ if(S.ch[i]==T.ch[j]){ i++; j++; }else{ k++; i = k; j = 1; } } if(j>T.length) return k; else return 0; }

时间复杂度

匹配成功：O(m)

匹配失败：O(n-m)

最坏时间复杂度：

匹配成功:O((n-m+1)*m)次，复杂度为O(nm)

简单模式匹配的思想

1，从主串中先逐个截取子串长度的串

2，截取串和子串匹配，如果不匹配，寻找下一个开头的子串

最坏时间复杂度:O(mn)

m-n轮的截取串都不匹配，每一次都会匹配一个子串的长度

截取串中，都是最后一个不匹配，这样每一轮都是匹配M次