string-searching.md

String Searching

KMP (knuth Morrison Pratt) Algorithm

private int kmpIndex(String string, String pattern) {
    int[] patternPrefix = patternPrefixArray(pattern);
    for (int t = 0, p = 0 ; t < string.length() && p < pattern.length() ; ) {
        if (string.charAt(t) == pattern.charAt(p)) {
            if (p == pattern.length() - 1) return t - p;
            p++;
            t++;
        } else if (p != 0) {
            p = patternPrefix[p - 1];
        } else {
            t++;
        }
    }
    return -1;
}

private int[] patternPrefixArray(String pattern) {
    int[] patternPrefix = new int[pattern.length()];
    for (int j = 0, i = 1 ; i  < pattern.length() && j < pattern.length() ; ) {
        if (pattern.charAt(j) == pattern.charAt(i)) {
            patternPrefix[i++] = j++ + 1;
        } else if (j == 0) {
            patternPrefix[i++] = 0;
        } else {
            j = patternPrefix[j - 1];
        }
    }
    return patternPrefix;
}

KMP Algorith Applied to List of Strings as text and pattern

public static void main(String[] args) {
        final List<String> text = List.of("apple", "apple", "orange", "banana", "apple", "banana");
        final List<String> pattern = List.of("apple", "apple", "banana");
        System.out.println(kmpIndex(text, pattern));
    }

    private static int kmpIndex(List<String> text, List<String> pattern) {
        int[] patternPrefix = patternPrefixArray(pattern);
        for (int t = 0, p = 0 ; t < text.size() && p < pattern.size() ; ) {
            if (text.get(t).equals(pattern.get(p))) {
                if (p == pattern.size() - 1) return t - p;
                p++;
                t++;
            } else if (p != 0) {
                p = patternPrefix[p - 1];
            } else {
                t++;
            }
        }
        return -1;
    }

    private static int[] patternPrefixArray(List<String> pattern) {
        int[] patternPrefix = new int[pattern.size()];
        for (int j = 0, i = 1 ; i  < pattern.size() && j < pattern.size() ; ) {
            if (pattern.get(j).equals(pattern.get(i))) {
                patternPrefix[i++] = j++ + 1;
            } else if (j == 0) {
                patternPrefix[i++] = 0;
            } else {
                j = patternPrefix[j - 1];
            }
        }
        return patternPrefix;
    }