单模式串匹配问题
问题定义
给出一个字符串T,称为模式串,再给出一个字符串S,称为原串,问模式串在原串中是否出现,出现位置都有哪些?
举个例子,T = “ha” ,S = “hahaschool” ,T在S中出现了两次,分别是S[0~1]和S[2~3](下标从0开始)。
朴素解法
很简单,只要枚举T在S中出现位置的起点和终点,然后再逐位把S中的字符和T中对应位置的字符比对,如果全部对应,就说明T在S的该段匹配。
优化解法
在暴力匹配中,如果发生了失配(S中的字符不等于T中对应位置的字符),那么我们将会放弃当前的匹配进度,直接从S的下一位开始匹配。如果我们可以保留一部分的匹配进度,就可以减少计算量。这种想法就是我们接下来要讲的KMP算法的源头。
KMP算法
求Next数组
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
const int MAXN = 1005; int nxt[MAXN]; void getNext (char *s, int len) { int i = 0, j = -1; nxt[0] = -1; while( i < len ) { if( j < 0 || s[i] == s[j] ) { ++i, ++j; if( s[i] == s[j] ) nxt[i] = nxt[j]; else nxt[i] = j; } else j = nxt[j]; } } |
使用Next数组加速字符串匹配
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
void KMP(char *t , char *s) { int tlen = strlen(t), slen = strlen(s); getNext (s,slen); int i = 0, j = 0; while( i < tlen ) { if( j < 0 || t[i] == s[j] ) { ++i, ++j; } else j = nxt[j]; } if( j <= 0 ) { puts("0"); }else { for( int i = 0; i < j; ++i ) putchar( s[i] ); putchar( ' ' ); printf("%d\n", j ); } } |