KMP笔记

Author Avatar
Sakits 8月 01, 2018

参考:https://www.cnblogs.com/yjiyjige/p/3263858.html

简介

  两个字符串进行匹配时,两个指针i,ji,j分别指着两个字符串的某个位置,表示这两个字符串匹配到了这两个位置。
enter image description here

enter image description here

  当失配时,暴力做法为将iijj都往回跑到下一次匹配的开始位置,重新匹配。

  这样显然是O(nm)O(nm)的。
  但是其实ii可以不动,在这个基础上让jj匹配到最长的距离。


  当前匹配位置:

  失配后:

  匹配串失配到的位置满足以其为开头以j1j-1结尾的字符串与匹配串前缀相同的长度最长,这个位置即fail[j]fail[j]

getfail()

  求失配函数fail[]fail[]其实就是拿自己去匹配自己。

inline void getfail()
{
	int j;
	for(int i=2;i<=m;i++)
	{
		for(j=fail[i-1];j && s2[j+1]!=s2[i];j=fail[j]);
		if(s2[j+1]==s2[i]) fail[i]=j+1;
		else fail[i]=0;
	}
}

匹配

  普通的两个字符串进行匹配,失配了就一直往回跳直到下一步能够匹配

inline void kmp()
{
	int j=0;
	for(int i=1;i<=n;i++)
	{
		for(;j && s2[j+1]!=s1[i];j=fail[j]);
		if(s2[j+1]==s1[i]) j++; else j=0;
		if(j==m) printf("%d\n", i-m+1);
	}
}