Boyer–Moore — bad-character rule

#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.

/* Boyer-Moore's bad-character rule only; no good-suffix preprocessing. */
void searchBM(const char text[], const char pattern[]) {
    int last[256], n = (int)strlen(text), m = (int)strlen(pattern), found = 0;

This program implements the bad-character rule only; it does not build a good-suffix table. last has one entry per byte value. n and m are text/pattern byte lengths, and found starts at zero.

    for (int c = 0; c < 256; ++c) last[c] = -1;
    for (int j = 0; j < m; ++j) last[(unsigned char)pattern[j]] = j;

Start every last entry at -1, meaning absent. Scan the pattern left to right and overwrite the entry, leaving its final index. Cast the byte to unsigned char for a nonnegative table index.

    for (int start = 0; start <= n - m;) {
        int j = m - 1;
        while (j >= 0 && pattern[j] == text[start + j]) --j;

start is the text alignment offset. Try only alignments where the full pattern fits. j begins at the final pattern character and moves left while bytes match.

        if (j < 0) {
            printf("Match at index %d\n",start); found = 1;
            start += start + m < n ? m - last[(unsigned char)text[start + m]] : 1;

j < 0 means all characters matched. Print start and set found. If a text byte exists immediately after the match, use its last occurrence in the pattern to choose a shift; otherwise advance by one. This can still report overlapping matches.

        } else {
            int shift = j - last[(unsigned char)text[start + j]];
            start += shift > 0 ? shift : 1;
        }
    }

Subtract the mismatching text byte’s last pattern position from j. Shift at least one even when that difference is not positive, ensuring progress. The braces finish the mismatch branch and alignment loop.

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

If no match set found, print the message. Otherwise the earlier match reports are sufficient.

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();
    searchBM(text,pattern); return 0;
}

Allow at most 1000 bytes per line, reject failed reads and an empty pattern, then call this bad-character implementation. The text itself may be empty; a longer pattern simply has no fitting alignment.