KMP算法——改进的模式匹配
主串为'a b a b c a b a a c b a b ',子串'a b c a c'
- 'a'前缀后缀都是空集，最长相等前后缀长度为0
- 'a b'前缀为{a}，后缀为{b}，{a}并{b}=空，最长相等前后缀长度为0
- 'a b c'前缀为{a,ab},后缀为{b,bc},{a,ab}并{c,cb}=空，最长相等前后缀长度为0
- 'a b c a'前缀为{a,ab,abc},后缀为{a,ac,acb},{a,ab,abc}并{a,ac,acb}={a}，最长度相等前后缀长为1
- 'a b c a c'前缀为{a,ab,abc,abca},后缀为{c,ac,cac,bcac},{a,ab,abc,abca}并{c,ac,cac,bcac} = 空，最长度相等前后缀长为0
字符串'abcac'的部分匹配值为00010
| 编号 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| s | a | b | c | a | c |
| next | 0 | 0 | 0 | 1 | 0 |
移动位数 = 已匹配的字符数 - 对应的部分匹配值
第一次匹配：
主串 a b a b c a b c a c b a b
子串 a b c
移动位数 = 2 - 0 = 2
第二次匹配：
主串 a b a b c a b c a c b a b
子串 a b c a c
移动位数 = 4 - 1 = 3
第三次匹配：
主串 a b a b c a b c a c b a b
子串 a b c a c
匹配
