模式匹配
对子串的定位操作通常被称为串的模式匹配
简单的说，就是对主串S的每一个字符作为子串开头，与要匹配的字符串T进行匹配，对主串S做大循环，每个字符开头做T的长度的小循环，直到匹配成功或者全部遍历完成为止
朴素的模式匹配算法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
//返回子串T在主串S中第pos个字符之后的位置，若不存在，返回0 //pos>=1 && pos <= length int Index(String S,String T,int pos) { int i = pos; int j = 1; while(i <= GetLength(S) && j <= GetLength(T)) { if(S[i] == T[i]) { ++i; ++j; } else { i = i-j+2; j = 1; } } if(j > GetLength(T)) return i-GetLength(T); else return 0; } |
KMP模式匹配算法
S串：abcdefgab
T串：abcdex
我们知道T串中首字符'a'与T串后面的字符均不相同。
而T串中的第二位'b'与S串的第二位'b'之前已经判断过是相等的，也就意味着，T串中的'a'与S串中的'b'是不需要判断，就可以确定它们是不可能相等的。
经过对比：
我们发现，在第一次大循环的时候，用i值来回溯到下一个位置（i-j+2），这种做法其实可以不需要的。
而KMP模式匹配算法，就是为了让没必要的回溯不发生。
继续分析：
既然i值不回溯，也就是不可以变小，那我们只能对j值考虑了。
通过观察，就可以发现，T串首字符与自身后面的字符的比较，如果发现有相同字符，那么j值的变化就会不相同。
也就是可以换句话说，这个j值的变化，其实与主串是没什么关系的，关键取决于T串的结构中是否有重复的问题
比如：
对于abcdex,j值由6变成了1
对于abcabx，j值由6变成了3
结论就是：
j值得多少取决于当前字符之前的串的前后缀的相似度
我们把T串各个位置的j值变化定义为一个数组next,那么不难理解，next的长度，就是T串的长度
推导next的数值组：
| j | 123456 |
| T | abcdex |
| next[j] | 011111 |
| j | 123456 |
| T | abcabx |
| next[j] | 011123 |
| j | 123456789 |
| T | ababaaaba |
| next[j] | 011234223 |
| j | 123456789 |
| T | aaaaaaaab |
| next[j] | 012345678 |
综上：
关于next[j],如果前后缀一个字符想等，k值是2，有2个相等，k值是3，n个相等k值就是n+1
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
//子串T的next数据 void get_next(String T,int * next) { int i,j; i = 0; j = 1; next[1] = 0; while(i < GetLength(T)) { if(j == 0 || T[i] == T[j])//T[i]表示后缀的单个字符，T[j]表示前缀的单个字符 { ++i; ++j; next[i] = j; } else j = next[j]; } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
int Index_KMP(String S,String T,int pos) { int i = pos; int j = 1; int next[255]; get_next(T,next); while(i <= GetLength(S) && j <= GetLength(T)) { if(j == 0 || S[i] == T[j]) { ++i; ++j; } else j = next[j]; } if(j > GetLength(T)) return i-GetLength(T); return 0; } |
KMP模式匹配算法改进
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
void get_nextval(String T,int * nextval) { int i,j; i = 0; j = 1; nextval[1] = 0; while(i < GetLength(T)) { if(j == 0 || T[i] == T[j]) { ++i; ++j; if(T[i] != T[j]) nextval[i] = j; else nextval[i] = nextval[j]; } else j = nextval[j]; } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
int Index_KMP(String S,String T,int pos) { int i = pos; int j = 1; int next[255]; get_nextval(T,next); while(i <= GetLength(S) && j <= GetLength(T)) { if(j == 0 || S[i] == T[j]) { ++i; ++j; } else j = next[j]; } if(j > GetLength(T)) return i-GetLength(T); return 0; } |
本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！
你可能也喜欢
- ♥ 排序_桶排序05/09
- ♥ 贪心算法06/29
- ♥ 数学知识模板03/09
- ♥ 匹配_有限自动机字符串匹配算法10/13
- ♥ 数据结构_二叉树节点10/16
- ♥ 排序_基数排序09/04
热评文章
- BFS和DFS 0
- 匹配_Rabin_karp匹配算法 0
- 排序_桶排序 0
- 狄克斯特拉算法 0
- 匹配_朴素字符串匹配算法 0
- 排序_计数排序 0