KMP字符串匹配算法
太久没写算法,KMP都忘了。。。
class Solution { public int strStr(String s, String p) { //s是父串,p是子串 int[] next = new int[p.length()]; //构建next int i =1,now =0; while(i<p.length()){ if(p.charAt(i)==p.charAt(now)){ now++; next[i] = now; i++; }else if(now!=0){ now = next[now-1]; }else{ next[i] = now; i++; } } System.out.print("next: "); for (int j = 0; j < next.length; j++) { System.out.print(next[j]+" "); } System.out.println(" "); //开始搜索 int tar =0,pos =0; while(tar<s.length()&&pos<p.length()){ if(s.charAt(tar)==p.charAt(pos)){ tar++; pos++; }else if(pos!=0){ pos=next[pos-1]; }else{ tar++; } } System.out.println(tar-pos); return pos==p.length()?tar-pos:-1; } }
本文系作者 @rinbn 原创发布在 噓だ。未经许可,禁止转载。