Naive String Matching

Exact pattern matching asks for every position where a pattern P occurs as a consecutive block inside text T. The naive method tries every possible starting position and directly compares the pattern characters. It is a useful first solution, a practical choice for small inputs, and an independent reference for testing more complicated linear-time methods.

This lesson reports 0-based positions, includes overlapping occurrences, preserves spaces, and defines an empty pattern to match at all N+1 text boundaries. Those choices are part of the problem contract. We will derive the loop bounds rather than relying on trial and error, then build an example that explains the method’s quadratic worst case.

Prerequisites: Introduction to String Algorithms; nested loops and vectors.

Build the idea

1. 1. Enumerate only starts that can fit

   Let N be text length and M pattern length. A nonempty match beginning at i needs positions i through i+M−1, so its final boundary i+M must be at most N. Thus starts are 0 through N−M inclusive. If M>N, there are no possible starts. For T=ababa and P=aba, only starts 0,1,2 can fit.

   At start 0 compare a with a, b with b, and a with a: report 0. At start 1, b differs from a immediately. At start 2 all three characters agree: report 2. The two occurrences overlap at text position 2. After a match, advance the starting position by one, not by M, when all occurrences are required.

2. 2. Prove the inner comparison

   Use j for the number of matched pattern characters at the current start i. Before each comparison, the first j pattern characters equal text[i..i+j). Initially j=0, so that claim holds trivially. If text[i+j] equals pattern[j], increment j and preserve the claim. If they differ, this start cannot be a full match. If j reaches M, all required characters agreed and i is a valid occurrence.

   This invariant also prevents out-of-range access: test j<M before reading pattern[j]. Since i≤N−M, every text position used by the inner loop is valid. Every reported start is correct, and every possible start is examined, so no occurrence is missed.

3. 3. Make empty-pattern behavior deliberate

   When M=0, matching means placing an empty block at a boundary. We report 0,1,…,N, including the boundary after the final character. With empty text and empty pattern, the only match is 0. With empty text and a nonempty pattern, there are no matches.

   The implementation’s regular loops already follow this policy: j starts at 0, which equals M, so every candidate boundary is recorded without reading a character. It first checks M≤N before computing N−M. In code using unsigned string sizes, subtracting a larger M from a smaller N can wrap to a huge value; the explicit guard prevents that error.

4. 4. Understand the worst case

   Let T contain N copies of a, and let P be M−1 copies of a followed by b. At each candidate start, the algorithm compares almost the entire pattern before failing. It performs (N−M+1)·M character comparisons. When M is about N/2, this is quadratic in N. Repeated characters are not a special corner to ignore: they expose how much information the algorithm throws away between neighboring starts.

   For random strings over a large alphabet, many starts fail at the first character, so observed performance may be much better. That does not change the guaranteed worst-case bound. Prefix-function and KMP lessons will reuse previous matches to avoid this repeated work.

5. 5. Use the reference responsibly

   The program first collects every starting position, then prints the count and a list. It prints −1 on the positions line if none exist; that marker is not a real position. For the sample, T=aaaaa and P=aaa, starts 0,1,2 all match and must all be included.

   Use this implementation to validate optimized matchers on short random texts, empty cases, all-equal strings, and patterns longer than the text. Avoid “testing” a matcher against another copy of the same algorithm; a simple independently written direct comparison is valuable precisely because it fails in different ways.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string text,pattern;
    getline(cin,text);
    getline(cin,pattern); // Spaces and blank lines are data.
    int n=static_cast<int>(text.size()),m=static_cast<int>(pattern.size());
    vector<int>matches;
    // Test fit before subtracting lengths; a longer pattern has no candidates.
    if(m<=n){
        for(int start=0;start<=n-m;++start){
            int j=0; // Exactly the first j characters agree at this start.
            while(j<m&&text[start+j]==pattern[j]){
                ++j;
            }
            if(j==m){
                matches.push_back(start); // Empty patterns match boundaries.
            }
            // Advancing start by one preserves overlapping occurrences.
        }
    }
    cout<<matches.size()<<'\n';
    if(matches.empty()){
        cout<<-1<<'\n';
    }
    else{
        for(int i=0;i<static_cast<int>(matches.size());++i){
            cout<<matches[i]<<(i+1==static_cast<int>(matches.size())?'\n':' ');
        }
    }
}

Complexity analysis

For 1≤M≤N, search costs O((N−M+1)M) time in the worst case, plus O(N+M) input reading. For M=0 there are N+1 outputs, requiring O(N) work; for M>N there are no candidate comparisons. Stored input uses O(N+M) space and the positions vector uses O(K), where K is the number of matches. Excluding input and output storage, search needs O(1) auxiliary space.

Example input and output

Line 1: text T. Line 2: pattern P. Either may be empty or contain spaces; each length is at most 1,000,000. Output match count and then all 0-based starts in increasing order, or −1 on the second line when none exist. Empty P matches every boundary.

Input

aaaaa
aaa

Output

3
0 1 2

Each block of three consecutive a characters is a match, including overlapping blocks. Starts 3 and 4 do not have enough remaining characters.

Practical applications

Small inputs, one-off checks, and correctness oracles for KMP/Z/hashing implementations. The same start-by-start framework can count mismatches, but then early stopping and complexity must be reconsidered.

Check your understanding

Why must the next candidate start after finding a match at i still be i+1?

Put it into practice

Change the matcher to count all starts having at most one mismatched character, keeping the pattern contiguous and the same fit rules.