Sunday, September 20, 2015

Implement strStr() using KMP

I'm reading "Introduction to Algorithms" to review the KMP algorithm. I feel the most important concept in the algorithm is k=pi[k]. It's very tricky to understand. The key to understand this is to remember for the matched part between target string and pattern string, checking target string is the same as checking pattern string. When constructing pi[], pattern string is both target string and pattern string. So apply the above rule again. Some notes per my understanding.



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