Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. 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.
  2. 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