Find all starting indices of pattern in text using Knuth-Morris-Pratt algorithm.
Input: text="AABAACAADAABAABA", pattern="AABA" → Output: [0,9,12]
Input: text="abcabc", pattern="abc" → Output: [0,3]
Build failure function (partial match table), then scan text using the table for efficient matching.
- Build lps[] (longest proper prefix which is also suffix) for pattern
- i=0 (text), j=0 (pattern)
- Match: i++, j++; at j==m: record index, j=lps[j-1]
- Mismatch: if j>0 set j=lps[j-1] else i++
- Return all match positions
public List<Integer> kmpSearch(String text, String pattern) {
List<Integer> result = new ArrayList<>();
int n = text.length(), m = pattern.length();
int[] lps = new int[m];
// Build LPS
for (int i = 1, len = 0; i < m; ) {
if (pattern.charAt(i) == pattern.charAt(len)) lps[i++] = ++len;
else if (len > 0) len = lps[len-1];
else lps[i++] = 0;
}
// Search
for (int i = 0, j = 0; i < n; ) {
if (text.charAt(i) == pattern.charAt(j)) { i++; j++; }
if (j == m) { result.add(i - j); j = lps[j-1]; }
else if (i < n && text.charAt(i) != pattern.charAt(j)) {
if (j > 0) j = lps[j-1]; else i++;
}
}
return result;
}
- Time Complexity: O(n+m)
- Space Complexity: O(m)