Brute-force exact pattern match

The brute force algorithm consists in checking, at all positions in the text between 0 and n-m, whether an occurrence of the pattern starts there or not. Then, after each attempt, it shifts the pattern by exactly one position to the right.

The brute force algorithm requires no preprocessing phase, and a constant extra space in addition to the pattern and the text. During the searching phase the text character comparisons can be done in any order. The time complexity of this searching phase is O(mn) (when searching for am-1b in an for instance). The expected number of text character comparisons is 2n.

Demonstration

In the following example we have to find the string in orange border (string to be find out) in the red border (source string)

Example

public class bruteForce {

	public static void main(String[] args) {

		String sourceString = "The quick brown fox jumps over the lazy dog";
		String toBeFindOut = "brown";

		// this will print location of starting word in the target string if found,
		// will print -1 otherwise
		System.out.println(search(toBeFindOut, sourceString));

	}

	public static int search(String pattern, String text) {
		int M = pattern.length();
		int N = text.length();
		for (int i = 0; i < N - M; i++) {
			int j;
			for (j = 0; j < M; j++)
				if (text.charAt(i + j) != pattern.charAt(j))
					break;
			if (j == M)
				return i; // pattern start index in text
		}
		return -1; // not found
	}
}

Output

10

Share

You may also like...