文档介绍：模式匹配与KMP算法
Zn
2006-4-9
*
OUTLINE
什么是模式匹配
朴素匹配算法
KMP算法
效率对比
更多模式匹配算法
2006-4-9
*
哪个是今天要讨论的模式匹配
the
The quick brown fox jumps over the lazy dog
jay
The quick brown fox jumps over the lazy dog
2006-4-9
*
模式匹配
Finding all occurrences of a pattern in a text
eg. 'abc' in 'acbcdabc'
2006-4-9
*
The naive string-matching algorithm
ababcabcacbab
abcac
How does it work?
2006-4-9
*
a b a b c a b c a c b a b
a b a b c a b c a c b a b
a b a b c a b c a c b a b
a b c a c
a b c a c
a b c a c
第一次匹配
第二次匹配
第三次匹配
2006-4-9
*
a b a b c a b c a c b a b
a b a b c a b c a c b a b
a b a b c a b c a c b a b
a b c a c
a b c a c
a b c a c
第六次匹配
第五次匹配
第四次匹配
2006-4-9
*
int Normal(int pos)
{
int i,j;
i=pos;j=0;
while(s[i]!=0&&j<length)
{
if(s[i]==t[j]){i++;j++;}
else{i=i-j+1;j=0;}
}
if(j==length)
return i-length;
else
return -1;
}
2006-4-9
*