实现函数 strStr。
函数声明如下:
char *strStr(char *str, char *dest)
返回一个指针,指向dest第一次在str中出现的位置,如果dest不是str的子串,则返回null
public class Solution { public String strStr(String str, String dest) { char[] t = str.toCharArray(); char[] p = dest.toCharArray(); if (p.length == 0) { return str; } int i = 0, j = 0; int[] next = getNext(dest); while (i < t.length && j < p.length) { if (j == -1 || t[i] == p[j]) { i++; j++; } else { j = next[j]; } } if (j == p.length) { return str.substring(i - j); } return null; } public static int[] getNext(String ps) { char[] p = ps.toCharArray(); int[] next = new int[p.length]; int j = 0; int k = -1; next[0] = -1; while (j < p.length - 1) { if (k == -1 || p[k] == p[j]) { if (p[++k] == p[++j]) { next[j] = next[k]; } else { next[j] = k; } } else { k = next[k]; } } return next; } }
//KMP这算法虽然知道原理,每次都忘怎么具体实现。。 public class Solution { public String strStr(String haystack, String needle) { if(needle.length() < 1) return haystack; if(haystack.length() < 1) return null; int[] nextval = getNext(needle.toCharArray()); int i = 0; int j = 0; while(i < haystack.length() && j < needle.length()) { if(j < 0 || haystack.charAt(i) == needle.charAt(j)) { i++; j++; } else { j = nextval[j]; } } if(j == needle.length()) return haystack.substring(i-j); else return null; } public int[] getNext(char[] ch) { int n = ch.length; int i = 0, j = -1; int[] nextval = new int[n]; nextval[0] = -1; while(i < n-1) { if(j == -1 || ch[i] == ch[j]) { i++; j++; if(ch[i] != ch[j]) { nextval[i] = j; } else nextval[i] = nextval[j]; } else j = nextval[j]; } return nextval; } }
public class Solution { public static String strStr(String haystack, String needle) { if(haystack == null || needle == null || needle.length() == 0) return haystack; if(needle.length() > haystack.length()) return null; for (int i = 0; i < haystack.length(); i ++ ) { if(haystack.charAt(i) == needle.charAt(0) && i + needle.length() <= haystack.length() && haystack.substring(i, i + needle.length()).equals(needle)) { return haystack.substring(i); } } return null; } }