()
| 11 | |
| 12 | |
| 13 | public int kmp() { |
| 14 | this.createLPS(); |
| 15 | int i = 0,j= 0; |
| 16 | |
| 17 | while(i<this.string.length() && j<this.pattern.length()) { |
| 18 | if(this.string.charAt(i) == this.pattern.charAt(j)) { |
| 19 | i++; |
| 20 | j++; |
| 21 | } |
| 22 | else if(j==0) { |
| 23 | i++; |
| 24 | } |
| 25 | else { |
| 26 | j = this.lps[j-1]; |
| 27 | } |
| 28 | |
| 29 | } |
| 30 | |
| 31 | if(j==pattern.length()) { |
| 32 | return i-pattern.length(); |
| 33 | } |
| 34 | |
| 35 | |
| 36 | return -1; |
| 37 | } |
| 38 | |
| 39 | |
| 40 | private void createLPS() { |