Java Solution using KMP Algorithm


  • 1

    The big idea of using KMP is when we meet a mismatch, we do not have to move the index of needle to 0, but to the index of suffix.

    public class Solution {
        public int strStr(String haystack, String needle) {
            char[] text = haystack.toCharArray(), pattern = needle.toCharArray();
            int[] lps = longestProperPrefix(pattern);
            int i = 0, j = 0;
            while(i < text.length && j < pattern.length) {
                if(text[i] == pattern[j]) {
                    i++;
                    j++;
                } else {
                    if(j != 0) j = lps[j - 1];
                    else i++;
                }
            }
            
            if(j == pattern.length) return i - pattern.length;
            else return -1;
        }
        
        private int[] longestProperPrefix(char[] pattern) {
            int[] lps = new int[pattern.length];
            int j = 0, i = 1;
            while(i < pattern.length) {
                if(pattern[i] == pattern[j]) {
                    lps[i++] = ++j;
                } else {
                    if(j != 0) j = lps[j - 1];
                    else i++;
                }
            }
            return lps;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.