对于KMP算法的next算法，匹配规则i不动，j而是根据
next[j]=k。如果在j位置失配，则退到k位置。构造next数组的
是根据前缀与后缀的最长匹配。。。如ababaa 的next数组是
-100123.
所以上述代码改成
match(string s, string p)
if s.length==0 || p.length==0
return -1;//-1表示找不到
if (p.length>s.length)
return -1
int i = 0
int j =0
int [] next = next(p)///求next数组
while(i<s.length)
if(j==-1 || s.charAt(i)==p.charAt(j)) //如果j=-1说明p的第一位无法匹配，是next[0]=-1
i++;
j++;
else
j=next[j]
if(j==p.length)
return (i-j)///这时候j最后，i也走到最后
return -1
所以时间复杂度是o（m+n）的复杂度
int [] next(string p)
int p_length = p.length
int [] next = new int[p.length]
char[] p = p.tochararray()
next[0]=-1
if(p.length==1)//进行判断防止下面越界
return next;
next[1]=0
int j=1
int k =next[j]//查看位置j的最长匹配在哪里
while(j<p.length-1)
if(k<0 || p[j]==p[k])//相等直接在原来基础上加一
next[++j] ==++k;
else ///不相等则回溯
k = next[k]
return next
next数组的含义，这个回退位置的前缀，和适配位置的后缀是一致才可以跳到j位置
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
