Naive Pattern Search

Naive pattern search^[1] is a string pattern matching algorithm which search a pattern or substring in another string.

Given a text $txt[0..n-1]$ and a pattern $pat[0..m-1]$. Write a function that print all occurrences of pat[] in txt[]. You may assume that $n>m$

Input : txt[] = "THIS IS A TEST TEXT"
				pat[] = "TEST"
Output: Pattern found at index 10


Input : txt[] = "AABAACAADAABAABA"
				pat[] = "AABA"
Output: Pattern found at index 0
				Pattern found at index 9
				Pattern found at index 12

Implementation

void patternSearch(string &pat, string &txt){
	int M = pat.size();
	int N = txt.size();
	int i;
	for (i = 0; i <= (N-M); i++){
		int j = 0;
		for (j = 0; j < M; j++) {
			if (txt[i+j] != pat[j]) break;
		}
		if (j == M) {
			cout << "pattern found at " << i << endl;
		}
	}
}

This algorithm start from comparing the first char in pat and the first char in txt. If the first char is different, then break to the next iteration. So the best case of this algorithm is the first char is significant to each char in txt.

The best cast time complexity is $O(N)$ which 1st char in pat do not match any char in txt. The worst cast is $O(M\ast N)$ which every char in pat occurs in every char in txt.

This algorithm doesn't need any extra space, so the space complexity is $O(1)$.

Follow Up

When a mismatch occurs after j matches, we know that the first char of pattern will not match the j matched chars because all chars of patterns are different.^[2]

We can always slide the pattern by j without missing any valid shifts.

void patternSearch(string &pat, string&txt) {
	int M = pat.size();
	int N = txt.size();
	for (int i = 0; i <= (N-M); i++) {
		for (int j = 0; j < M; j++) {
			if (txt[i+j] != pat[j]) break;
			if (j == M) {
				cout << "pattern found at index " << i << endl;
				i = i + M;
			} else if (j == 0) {
				i = i + 1;
			} else {
				i = i + j; // slide the pattern by j
			}
		}
	}
}