Code for strstr, which is also a leetcode question.
1: public int strStr(String haystack, String needle) {
2: int l = needle.length();
3: if(l == 0)
4: return 0;
5: int[] pie = new int[l];
6: pie[0] = 0;
7: int k = 0;
8: for(int q = 1; q < l; q++) {
9: while(k>0 && needle.charAt(k)!=needle.charAt(q))
10: k = pie[k-1];
11: if(needle.charAt(k) == needle.charAt(q))
12: k++;
13: pie[q] = k;
14: }
15: int i = 0;
16: int j = 0;
17: while(i < haystack.length()) {
18: while(j>0 && needle.charAt(j)!=haystack.charAt(i))
19: j = pie[j-1];
20: if(needle.charAt(j) == haystack.charAt(i))
21: j++;
22: if(j == needle.length())
23: return i-j+1;
24: i++;
25: }
26: return -1;
27: }
No comments:
Post a Comment