Knuth–Morris–Pratt pattern matching

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <errno.h>

stdio.h supplies terminal input/output. stdlib.h declares conversion and allocation functions. string.h supplies string and memory utilities. ctype.h supplies isspace, and errno.h supplies conversion error reporting. Headers declare facilities; including them does not execute an operation.

/* Read one entire token; reject malformed, oversized and out-of-range input. */
int readToken(char text[], size_t capacity) {
    int ch; size_t used = 0; int fits = 1;

readToken receives a writable buffer and its capacity. ch is int so it can represent EOF as well as input characters. used counts stored characters, and fits starts as a success flag. One slot must remain for the null terminator.

    while ((ch = getchar()) != EOF && isspace((unsigned char)ch)) { }
    if (ch == EOF) return 0;

Read until a non-whitespace character appears. The unsigned-char cast supplies an allowed value to isspace. Return 0 if EOF arrives before a token begins.

    do {
        if (ch == 0) fits = 0;
        if (used + 1 < capacity) text[used++] = (char)ch;
        else fits = 0;

The do body handles the character already read. An embedded zero byte marks the token invalid. Store a character only while there is room for it and a null terminator; otherwise clear fits. Continue reading even after the buffer fills.

        ch = getchar();
    } while (ch != EOF && !isspace((unsigned char)ch));
    text[used] = '\0';
    return fits;
}

Read through the next whitespace or EOF, add a null character after the stored prefix, then return fits. A too-long token returns 0 rather than pretending that its stored prefix is the complete token.

int readInt(int *value) {
    char token[64], *end;
    if (!readToken(token, sizeof token)) return 0;

value is an output address. A 64-slot local buffer receives the token; a failed token read returns 0 before attempting conversion.

    errno = 0; long result = strtol(token, &end, 10);
    if (errno || end == token || *end || result < -1000000 || result > 1000000) return 0;

Reset errno before strtol. &end receives the stopping address. Reject conversion errors, no converted digits, leftover characters, or values outside -1,000,000 to 1,000,000. Thus 12x is not accepted as the integer 12.

    *value = (int)result; return 1;
}
int invalid(void) { puts("Invalid or incomplete input."); return 1; }

Store a validated integer through *value and return 1 from readInt. invalid is a separate helper that prints the error and returns 1 as main’s failure status; the same number has different roles in these two function contracts.

#define MAX_TEXT 1000
int readLine(char text[], size_t capacity) {
    size_t used = 0; int ch, pending = EOF, fits = 1, seen = 0;

MAX_TEXT is 1000. readLine tracks used slots, capacity status and whether any character was seen. pending starts at EOF as a marker that no character is waiting to be stored.

    while ((ch = getchar()) != EOF && ch != '\n') {
        seen = 1;
        if (ch == 0) fits = 0;
        /* Delay one byte so a final CR is a terminator, not line content. */

Read characters until newline or EOF and mark that input was seen. A zero byte makes fits false. The comment explains why one byte is delayed: a final carriage return can belong to the line ending rather than the text.

        if (pending != EOF) {
            if (used + 1 < capacity) text[used++] = (char)pending;
            else fits = 0;
        }
        pending = ch;
    }

If a pending byte exists, append it only while buffer space remains; otherwise mark overflow. Then hold the newly read byte in pending. This consumes the complete line even after a capacity problem.

    if (pending != EOF && pending != '\r') {
        if (used + 1 < capacity) text[used++] = (char)pending;
        else fits = 0;
    }

At the line end, preserve the pending byte only if it is real content. A final carriage return is omitted, supporting CRLF line endings. The capacity test still reserves a null-terminator slot.

    text[used] = '\0';
    return fits && (ch == '\n' || seen);
}

Store the null terminator. Success requires fits and either a newline or at least one seen character. A blank newline is a valid empty text line; EOF before any character is not an input line.

void buildLPS(const char pattern[], int m, int lps[]) {
    lps[0] = 0;
    for (int i = 1, length = 0; i < m;) {
        if (pattern[i] == pattern[length]) lps[i++] = ++length;

lps[0] is zero. For each later position i, length tracks the candidate proper-prefix length. A character match extends that prefix and stores its new length in lps before advancing i.

        else if (length) length = lps[length - 1];
        else lps[i++] = 0;
    }
}

On a mismatch with a nonzero candidate length, replace length with lps[length - 1] and retry the same i. If length is already zero, store zero and advance. A proper prefix never includes the whole current substring.

void searchKMP(const char text[], const char pattern[]) {
    int n = (int)strlen(text), m = (int)strlen(pattern), lps[MAX_TEXT], found = 0;
    buildLPS(pattern,m,lps);
    printf("LPS:"); for (int k = 0; k < m; ++k) printf(" %d", lps[k]); putchar('\n');

Measure text and the nonempty pattern, allocate a bounded lps array, build it, then print its m entries. found begins at zero for the final no-match report.

    for (int i = 0, j = 0; i < n;) {
        if (text[i] == pattern[j]) { ++i; ++j; }
        else if (j) j = lps[j - 1];
        else ++i;

i is the text index and j the matched-pattern length. Matching characters advance both. A mismatch with j > 0 changes only j via lps, so the same text character is reconsidered. With j == 0, advance the text index.

        if (j == m) {
            printf("Match at index %d\n",i - m); found = 1; j = lps[j - 1];
        }
    }

When j equals m, the starting index is i - m. Set found and fall back to lps[j - 1] rather than restarting at zero; a suffix of this match may begin the next overlapping occurrence.

    if (!found) puts("No match.");
}

The found flag suppresses No match after any successful occurrence. The brace ends searchKMP.

/* Text line, then nonempty pattern line; each at most 1000 bytes. */
int main(void) {
    char text[MAX_TEXT + 1], pattern[MAX_TEXT + 1];
    if (!readLine(text,sizeof text) || !readLine(pattern,sizeof pattern) || !pattern[0]) return invalid();
    searchKMP(text,pattern); return 0;
}

main reserves space for 1000 bytes plus a terminator in each buffer. Text may be empty, but pattern[0] must not be null. Call KMP only after both line reads succeed, then return success. Positions count bytes, not Unicode characters.