KMPITeye - 凯时娱乐

KMPITeye

2019年03月13日08时30分43秒 | 作者: 向山 | 标签: 匹配,长串,短串 | 浏览: 2934

字符串匹配:KMP,就是给出一个长串T,给出一个短串P,求T是否包括子串P,若包括,输出榜首个子串的方位。不然输出-1。

首要假定i是T的指针,j是P的指针。
关于传统的匹配形式,每逢T[i] != P[j]时,咱们会把j变成0,i跳回到方才匹配的开始方位的下一个方位从头进行匹配,这样复杂度是O(n*m).

可是关于KMP思维,能够先结构一个next数组,next[j] = k 表明,短串中的子串0 ~ j的串中,以P[j]结束的后缀串,与该子串中以P[0]最初的前缀串重复时,k的方位。
即有P[0] ~ P[k] = P[j - k] ~ P[j].

这样,在匹配过程中当短串匹配到j,长串匹配到了i,然后下一个字符不匹配,那么其实P[0] ~ P[j] 是与 T[i - j] ~ T[i]是匹配的。那么,咱们使用短串中后缀与前缀的联系,让下一次匹配的方位变成next[j].假定next[j] = k,那么其实短串中的P[0] ~ P[k]是现已与长串中的T[i - k] ~ T[k]是匹配过的了(一开始与后缀匹配成功了,而这个前缀和后缀是相同滴)。所以就这样匹配下去了。


//////////////////////////////////////
别的留意的是,得到的后缀和前缀的长度都是k,且这个k应该是最长的,能满意前缀和后缀持平的值。由于KMP匹配过程中,长串的指针j是不需求回溯的,所以咱们要确保能使用到j前面那些匹配成功的字符。

假如不是k最长的反例:
假定长串aaaaaab
  短串aaaaab
若令next[0] = next[5] = -1 ; next[1] ~ next[4] = 0;
则会发现回来的成果是匹配不成功。
(由于长串的指针不回溯,需求使用到前面那段匹配过的成果)
///////////////////////////////////////////

言归正传,KMP,下面是关于整型的状况(HDU 1711)
void get_next(int *p, int *next) //p是短串
 int i = 1, j = 0;
 next[0] = -1;
 while (i m) //m是短串长度
 if (p[i]  p[j])
 next[i] = j;
 j++;
 else
 if (p[i]  p[0])
 next[i] = 0;
 j = 1;
 else
 next[i] = -1;
 j = 0;
 ++i;
void kmp()
 int i = 0, j = 0;
 while (i n) //n是长串长度
 if (T[i]  P[j]) //P是短串,T是长串
 if (j  m - 1)
 printf("%d\n", i - j + 1);
 break;
 ++i, ++j;
 else
 if (j  0)
 j = 0;
 i++;
 else j = nex[j - 1] + 1;
 if (i  n) printf("-1\n");
}
版权声明
本文来源于网络,版权归原作者所有,其内容与观点不代表凯时娱乐立场。转载文章仅为传播更有价值的信息,如采编人员采编有误或者版权原因,请与我们联系,我们核实后立即修改或删除。

猜您喜欢的文章