Find the list of starting indexes of occurring of a string in another string in O(N) time complexity

Question

Given are two strings : str1 and str2. Find all the starting indexes of str1 in str2. Example: I/p = str1: abc, str2: abckdabcgfacabc O/p = [0, 5, 12]

public static List<Integer> firstMatchingIndexes(String str1, String str2) {
    List<Integer> indexes = new ArrayList<>();
    int end = 0, n = str2.length();
    
    for(; end<n; end++) {
        int index = str2.substring(end, n).indexOf(str1)+end;
        if(index!=-1)
            indexes.add(index);
        else
            break;
        end =index + str1.length()-1;
        
    }
    
    return indexes;
}

But this approach uses indexOf() which internally has O(N) time complexity. Can KMP algorithm work here?

Answer 1

Yes, the Knuth–Morris–Pratt algorithm can be of use here.

The Wikipedia article on the Knuth–Morris–Pratt algorithm provides pseudocode for the algorithm. Here is that pseudocode ported to Java:

    static int[] kmpTable(String pattern) {
        int n = pattern.length();
        int[] partialMatchTable = new int[n+1];
        int j = 0;

        partialMatchTable[0] = -1;

        for (int i = 1; i < n; i++, j++) {
            if (pattern.charAt(i) == pattern.charAt(j)) {
                partialMatchTable[i] = partialMatchTable[j];
            } else {
                partialMatchTable[i] = j;
                while (j >= 0 && pattern.charAt(i) != pattern.charAt(j)) {
                    j = partialMatchTable[j];
                }
            }
        }
        partialMatchTable[n] = j;
        return partialMatchTable;
    }
 
    static List<Integer> kmpSearch(String needle, String haystack) {
        List<Integer> matches = new ArrayList<>();
        int m = haystack.length();
        int n = needle.length();
        if (n > m) { // Added this to avoid O(m) runtime
            return matches; // Return empty list when needle is too large
        }
        int[] partialMatchTable = kmpTable(needle);
        int j = 0, k = 0;

        while (j < m) {
            if (needle.charAt(k) == haystack.charAt(j)) {
                j++;
                k++;
                if (k == n) {
                    matches.add(j - k);
                    k = partialMatchTable[k];
                }
            } else {
                k = partialMatchTable[k];
                if (k < 0) {
                    j++;
                    k++;
                }
            }
        }
        return matches;
    }

    public static void main(String args[])
    {
        System.out.println("matches: " + kmpSearch("abc", "abckdabcgfacabc"));
    }

This outputs:

matches: [0, 5, 12]

Wikipedia says about the time complexity:

the Knuth–Morris–Pratt algorithm has complexity O(), where is the length of .

And when taking into account the time needed for building the partial-match table for a pattern of length :

Since the two portions of the algorithm have, respectively, complexities of O() and O(), the complexity of the overall algorithm is O( + ).

We can however say it is O() when ≤ . When searching with a pattern that is longer than the string to search in, the algorithm could just skip building the partial match table for such a search string and exit with an empty list (See commented code that is not present in Wikipedia's pseudocode). That way it is always O().

Answer 2

I was able to get the following algorithm to render.

Correct me if I'm wrong; I believe this is an example of O(n) complexity.
As for a KMP algorithm, I'm unsure.

List<Integer> firstMatchingIndexes(String stringA, String stringB) {
    List<Integer> indices = new ArrayList<>();
    boolean checking = false;
    int indexA = 0, indexB = 0;
    for (char character : stringB.toCharArray()) {
        if (checking) {
            if (character == stringA.charAt(indexA))
                if (indexA != stringA.length() - 1)
                    indexA++;
                else {
                    indices.add(indexB - (stringA.length() - 1));
                    checking = false;
                    indexA = 0;
                }
            else {
                checking = false;
                indexA = 0;
            }
        } else if (character == stringA.charAt(indexA)) {
            checking = true;
            indexA++;
        }
        indexB++;
    }
    return indices;
}

Output

[0, 5, 12]