This document outlines the implementation and usage of the Knuth-Morris-Pratt (KMP) algorithm for efficiently finding all occurrences of a pattern string within a larger text string. The algorithm is designed to handle texts and patterns composed of uppercase and lowercase English letters, aswell as Arabic numerals.

Problem Statement

Given a text string $S$ and a pattern string $P$, identify all starting indices where $P$ appears as a substring within $S$. Indices are zero-based.

Input Format

• The first line contains an integer $N$, the length of the pattern string $P$.
• The second line contains the pattern string $P$.
• The third line contains an integer $M$, the length of the text string $S$.
• The fourth line contains the text string $S$.

Output Format

A single line containing the space-separated starting indices of all matches. Indices are zero-based.

Constraints

• $1 \le N \le 10^5$
• $1 \le M \le 10^6$

Example

Input:

3
aba
5
ababa

Output:

0 2

Algorithm Implementation

The KMP algorithm preprocesses the pattern to build a "failure function" (often denoted as next or lps - longest proper prefix suffix array). This function helps to avoid redundant comparisons by leveraging information about the pattern's internal structure. When a mismatch occurs during pattern matching, the failure function dictates how far to shift the pattern to the right.

Failure Function Calculation

The failure function, ne, for a pattern $P$ of length $N$ is an array where ne\[i\] stores the length of the longest proper prefix of $P[1..i]$ that is also a suffix of $P[1..i]$.

#include <iostream>
#include <vector>

const int MAX_PATTERN_LEN = 100010;
const int MAX_TEXT_LEN = 1000010;

int failure_function[MAX_PATTERN_LEN];
char pattern[MAX_PATTERN_LEN];
char text[MAX_TEXT_LEN];

void compute_failure_function(int n) {
    for (int i = 2, j = 0; i <= n; ++i) {
        // If characters don't match, backtrack j using the failure function
        while (j > 0 && pattern[i] != pattern[j + 1]) {
            j = failure_function[j];
        }
        // If characters match, advance j
        if (pattern[i] == pattern[j + 1]) {
            j++;
        }
        failure_function[i] = j;
    }
}

Pattern Matching

Once the failure function is computed, we can iterate through the text. Pointers i for the text and j for the pattern are used. If characters match, both pointers advance. If a mismatch occurs, the j pointer is updated using the failure function, effectively shifting the pattern.

#include <iostream>
#include <vector>

// Assuming compute_failure_function is defined as above
// ...

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m; // n: pattern length, m: text length

    // Read pattern (using 1-based indexing for convenience with failure function)
    std::cin >> n;
    for (int i = 1; i <= n; ++i) {
        std::cin >> pattern[i];
    }

    // Read text (using 1-based indexing)
    std::cin >> m;
    for (int i = 1; i <= m; ++i) {
        std::cin >> text[i];
    }

    // Compute the failure function for the pattern
    compute_failure_function(n);

    // Perform pattern matching
    for (int i = 1, j = 0; i <= m; ++i) {
        // While mismatch and j is not at the beginning of the pattern, backtrack j
        while (j > 0 && text[i] != pattern[j + 1]) {
            j = failure_function[j];
        }
        // If characters match, advance j
        if (text[i] == pattern[j + 1]) {
            j++;
        }
        // If j reaches the length of the pattern, a match is found
        if (j == n) {
            // Output the starting index (0-based) of the match
            printf("%d ", i - n);
            // After a full match, reset j using the failure function
            // to find overlapping matches
            j = failure_function[j];
        }
    }
    printf("\n"); // Ensure output ends with a newline

    return 0;
}

The code reads the pattern and text, computes the KMP failure function, and then iterates through the text to find all occurrences of the pattern. When a complete match is found (i.e., j equals the pattern length n), the starting index of the match in the text is printed. The j pointer is then reset using failure\_function\[j\] to allow for the detection of overlapping matches.