Skip to content

Instantly share code, notes, and snippets.

@cedric-sun
Created December 25, 2019 22:22
Show Gist options
  • Save cedric-sun/67b96820767ab8f05cae76a7a76bc96f to your computer and use it in GitHub Desktop.
Save cedric-sun/67b96820767ab8f05cae76a7a76bc96f to your computer and use it in GitHub Desktop.
weird leetcode 28 java NPE
class Solution {
public int strStr(String haystack, String needle) {
if (needle.isEmpty()) return 0;
return new KMPOptimized(haystack,needle).kmp();
}
class KMPOptimized {
String text;
String pattern;
int[] T;
public KMPOptimized(String text, String pattern) {
this.text = text;
this.pattern = pattern;
int[] T = new int[this.pattern.length()];
}
private void computeT() {
T[0] = -1;
int pos = 1, cnd = 0;
while (pos < pattern.length()) {
if (pattern.charAt(pos) == pattern.charAt(cnd))
T[pos] = T[cnd];
else {
T[pos] = cnd;
cnd = T[cnd];
while (cnd >= 0 && pattern.charAt(pos) != pattern.charAt(cnd)) {
cnd = T[cnd];
}
}
pos++;
cnd++;
}
T[pos] = cnd;
}
int kmp() {
computeT();
int i = 0, j = 0;
while (i < text.length()) {
if (text.charAt(i) == pattern.charAt(j)) {
i++;
j++;
if (j == pattern.length()) {
return i - j;
}
} else {
// if (j == 0)
// i++;
// else
// j = T[j - 1];//wow
j = T[j];
if (j<0) {
i++;
j++;
}
}
}
return -1;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment