KMP algorithm for pattern matching


  • 0
    A

    Given two strings
    data: "thisisatest"
    search " is"
    find the first index of the occurence of search string in the given data string.
    What is the given data string is a million characters long?


  • 1
    R

    ...

    static int firstOccurance(String input, String str) {
        List<String> matches = new ArrayList<String>();
        for(int i=0; i<input.length();i++) {
        char nextInput = input.charAt(i);
            for(int j=0;j<matches.size();j++) {
                String strIndex= matches.get(j);
                if(nextInput == str.charAt(strIndex.length())) {
                    matches.set(j, strIndex+nextInput);
                    if((strIndex+nextInput).equals(str)) {
                    return i-str.length()+1;
                    }
                } else {
                 matches.remove(j);
                }
            }
            if(nextInput == str.charAt(0)) {
                    if(str.length() == 1) {
                    return i-str.length()+1;
                    }
                    matches.add(String.valueOf(nextInput));
             }     
        }
        return -1;
    }
    

    ...


Log in to reply
 

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