Practice › Strings
Find All Pattern Occurrences
Medium · Strings · Asked at Amazon, Google, Microsoft, Codenation
Find every position where pattern occurs in text (occurrences may overlap). Print how many there are, and on the next line their 1-based starting positions in increasing order. If there are none, print only 0.
Input
First line: text. Second line: pattern. Both contain only lowercase letters.
Output
The count, then the positions (only if the count is not 0).
Constraints
- 1 ≤ |pattern| ≤ |text| ≤ 10^6
A naive check is O(n·m). KMP (prefix function) or Z-algorithm finds all matches in O(n + m).
Example 1
Input
abababab abab
Output
3 1 3 5
Example 2
Input
hello xyz
Output
0
Hints
- Compute the prefix function (failure function) of the pattern: pi[i] = length of the longest proper prefix of pattern[0..i] that is also a suffix of it.
- Scan the text keeping the current matched length; on a mismatch fall back with pi instead of restarting. When the matched length reaches m, record a match and fall back once more to allow overlaps.
Approach
KMP. Build pi for the pattern in O(m). Then walk the text with k = characters matched so far: while k > 0 and the next characters differ, set k = pi[k-1]; if they match, k++. When k == m, a match ends here — its start is i − m + 2 (1-based) — then set k = pi[k-1] so overlapping matches are found. Every character of the text is processed in amortised O(1).
Complexity: O(n + m) time · O(m) space (plus the output)
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string text, pat;
cin >> text >> pat;
int n = text.size(), m = pat.size();
vector<int> pi(m, 0);
for (int i = 1, k = 0; i < m; i++) {
while (k > 0 && pat[i] != pat[k]) k = pi[k - 1];
if (pat[i] == pat[k]) k++;
pi[i] = k;
}
vector<int> pos;
for (int i = 0, k = 0; i < n; i++) {
while (k > 0 && text[i] != pat[k]) k = pi[k - 1];
if (text[i] == pat[k]) k++;
if (k == m) {
pos.push_back(i - m + 2);
k = pi[k - 1];
}
}
cout << pos.size() << "\n";
for (size_t i = 0; i < pos.size(); i++) cout << pos[i] << (i + 1 < pos.size() ? " " : "\n");
return 0;
}Python solution
import sys
text, pat = sys.stdin.read().split()[:2]
n, m = len(text), len(pat)
pi = [0] * m
k = 0
for i in range(1, m):
while k and pat[i] != pat[k]:
k = pi[k - 1]
if pat[i] == pat[k]:
k += 1
pi[i] = k
pos, k = [], 0
for i, c in enumerate(text):
while k and c != pat[k]:
k = pi[k - 1]
if c == pat[k]:
k += 1
if k == m:
pos.append(i - m + 2)
k = pi[k - 1]
print(len(pos))
if pos:
print(*pos)Java solution
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String text = br.readLine().trim(), pat = br.readLine().trim();
int n = text.length(), m = pat.length();
int[] pi = new int[m];
for (int i = 1, k = 0; i < m; i++) {
while (k > 0 && pat.charAt(i) != pat.charAt(k)) k = pi[k - 1];
if (pat.charAt(i) == pat.charAt(k)) k++;
pi[i] = k;
}
StringBuilder sb = new StringBuilder();
int count = 0;
for (int i = 0, k = 0; i < n; i++) {
while (k > 0 && text.charAt(i) != pat.charAt(k)) k = pi[k - 1];
if (text.charAt(i) == pat.charAt(k)) k++;
if (k == m) {
sb.append(count++ == 0 ? "" : " ").append(i - m + 2);
k = pi[k - 1];
}
}
System.out.println(count);
if (count > 0) System.out.println(sb);
}
}Solve Find All Pattern Occurrences online · All practice problems