字符串模式匹配KMP算法详解.doc
需积分: 13 82 浏览量
2012-05-24
13:15:46
上传
评论
收藏 211KB DOC 举报
一句话理解朴素模式匹配算法：当两个字符串比较字符不匹配时，子串回溯到
起始位置，主串回溯子串长度的下一个位置
一句话理解 KMP 算法：当两个字符串比较字符不匹配时，主串不回溯，子串
回溯到 next[j]位置
KMP 字符串模式匹配详解
KMP 字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高
效算法。简单匹配算法的时间复杂度为 O(m*n);KMP 匹配算法。可以证明它的
时间复杂度为 O(m+n).。
一.简单匹配算法
先来看一个简单匹配算法的函数：
int Index_BF ( char S [ ], char T [ ], int pos )
{
/* 若串 S 中从第 pos(S 的下标 0≤pos<StrLength(S))个字符
起存在和串 T 相同的子串，则称匹配成功，返回第一个
这样的子串在串 S 中的下标，否则返回 -1 */
int i = pos, j = 0;
while ( S[i+j] != '/0'&& T[j] != '/0')
if ( S[i+j] == T[j] )
j ++; // 继续比较后一字符
else
{
i ++; j = 0; // 重新开始新的一轮匹配
}
if ( T[j] == '/0')
return i; // 匹配成功]] 返回下标
else
return -1; // 串 S 中(第 pos 个字符起)不存在和串 T 相同的子串
} // Index_BF
此算法的思想是直截了当的：将主串 S 中某个位置 i 起始的子串和模式串 T 相
比较。即从 j=0 起比较 S[i+j] 与 T[j]，若相等，则在主串 S 中存在以 i 为起始位
置匹配成功的可能性，继续往后比较( j 逐步增 1 )，直至与 T 串中最后一个字符
剩余14页未读，继续阅读
评论0
最新资源