String Search: Brute Force
August 21, 2009
In this exercise, and several that will follow, we will examine algorithms for searching a string. Our goal is to write a function that takes a pattern and a string and either returns the index of the first location of the pattern or an indication that the pattern is not present in the string; an optional third argument allows the search to start at an arbitrary point in the string. Our pattern is simply a fixed string; unlike regular expressions, there are no meta-characters.
Our first string-search algorithm uses brute force: place the pattern at each possible location in the search string and compare character-by-character to determine if there is a match.
Your task is to write a function that performs brute-force string searching as described above. Since we will be writing several other string searching functions, you should also write a test suite that will find any errors in your function. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
[…] Praxis – Brute Force By Remco Niemeijer Today’s Programming Praxis post is another easy one. We have to implement a brute-force string search. […]
My Haskell solution (see http://bonsaicode.wordpress.com/2009/08/21/programming-praxis-brute-force/ for a version with comments):
import Data.List bruteSearch :: Eq a => [a] -> Maybe Int -> [a] -> Maybe Int bruteSearch n o = fmap fst . find (isPrefixOf n . snd) . drop (maybe 0 id o) . zip [0..] . tails test :: (String -> Maybe Int -> String -> Maybe Int) -> IO () test f = do print $ f "" Nothing "Hello World" == Just 0 print $ f "He" Nothing "Hello World" == Just 0 print $ f "od" Nothing "Bonsai Code" == Just 8 print $ f "ef" Nothing "Bonsai Code" == Nothing print $ f "" (Just 1) "Hello World" == Just 1 print $ f "He" (Just 1) "Hello World" == Nothing print $ f "od" (Just 1) "Bonsai Code" == Just 8 print $ f "ef" (Just 1) "Bonsai Code" == Nothing main :: IO () main = test bruteSearch> we use a Scheme idiom to conflate the two loops into a single loop.
Could you please explain for non-Schemers? Looks interesting.
In imperative languages, the loops would be written something like
for (s=0; s<slen; s++) {
… body2a …
for (p=0; p<plen; p++) {
… body1 …
}
… body2b …
}
There may be some kind of goto inside the inner loop, perhaps disguised as a break or continue or return statement.
In Scheme, a named let of the form
(let loop ((p 0) (s 0)) … body …)
creates a function named loop that takes two arguments, p and s, then calls loop with initial values 0 and 0. Then control proceeds by recursion, with loop calling itself as needed. The trick is that either or both of the arguments can be altered at each call. We took advantage of that above. (loop (+ p 1) (+ s 1)) updates both p and s; (loop 0 (- s p -1)) starts a new p-loop and sets s as needed.
Ruby:
require 'enumerator' def brute_force_match(target, pattern) t = target.split('') # convert to list of chars index = 0 t.each_cons(pattern.length) do |slice| substring = slice.join return index if substring == pattern index += 1 end nil endAnd unit tests:
require ‘bruteforce’ #code to test
require ‘test/unit’
class TestBruteForce < Test::Unit::TestCase def setup @string = 'The Quick Brown Fox' end def tests assert_equal(brute_force_match(@string, 'T'), 0) assert_equal(brute_force_match(@string, 'The'), 0) assert_equal(brute_force_match(@string, 'x'), 18) assert_equal(brute_force_match(@string 'Fox'), 16) assert_equal(brute_force_match(@string, 'o'), 12) assert_nil(brute_force_match(@string, '@')) end end [/sourcecode]
Thanks for explaining the named let idiom!
Please delete my previous comment.
I posted it too soon before reading the ‘How to post source code’ document.
static int BruteForceStringSearch(string strInput, string strSearch)
{
int iSearchStringPos = -1; //String not found
int iPos = 0;
int iLastPosToCheck = 0;
int iSearchLen = strSearch.Length;
if (strSearch.Length <= strInput.Length) { iLastPosToCheck = strInput.Length - strSearch.Length; while (iPos <= iLastPosToCheck) { if (strSearch == strInput.Substring(iPos, iSearchLen)) { iSearchStringPos = iPos + 1; break; } else { iPos++; } } } return iSearchStringPos; } Debug.Assert(BruteForceStringSearch("abcde", "abcde") == 1); Debug.Assert(BruteForceStringSearch("abcde", "a") == 1); Debug.Assert(BruteForceStringSearch("abcde", "e") == 5); Debug.Assert(BruteForceStringSearch("abcde", "cd") == 3); Debug.Assert(BruteForceStringSearch("abcde", "abcdef") == -1); Debug.Assert(BruteForceStringSearch("abcde", "xyz") == -1); [/sourcecode]
Well, at first I tried to be clever, but it turns out I was not as clever as I hoped: http://codepad.org/aKnZc29H (this breaks if you try searching for “mi”).
Anyway, here’s my (hopefully) working solutions in D. I created a nested function similar to your scheme approach (if I read it right), a while loop that uses basically the same algorithm, and the nested loops as you suggested. http://codepad.org/2s9Mfe9F
Common lisp version, I don’t grok loop enough to loop over both indicies at the same time.
(defun check-match (target string)
(cond ((= 0 (length target)) t)
((= 0 (length string)) nil)
((< (length string) (length target)) nil) (t (loop for i from 0 below (length target) if (not (eql (char target i) (char string i))) do (return nil) finally (return t))))) (defun string-search-brute-force (target string) "Search for target in string, returning the index of first occurrence, or nil if not found." (loop for i from 0 below (length string) if (check-match target (subseq string i)) do (return i) finally (return nil))) (defun run-tests () (progn (assert (eq (string-search-brute-force "" "foo") 0)) (assert (eq (string-search-brute-force "foo" "") NIL)) (assert (eq (string-search-brute-force "foo" "bar") NIL)) (assert (eq (string-search-brute-force "foo" "barfoo") 3)) (assert (eq (string-search-brute-force "fo" "foo") 0)) (assert (eq (string-search-brute-force "foo" "barfo") NIL)) )) [/sourcecode]
implemented in C
/* search pattern in a string using brute force */ int string_index(char *s, char *p, int pos) { int i; char *q, *strp, *patp; /* move s to pos */ for(i = 1, q = s; *q != '\0' && i < pos; i++, q++); /* search pattern */ for(; *q != '\0'; q++) { for(strp = q, patp = p; *strp == *patp && *patp != '\0'; strp++, patp++); if(*patp == '\0') return q-s+1; } return -1; }Here its python workout:
def brute_force(pattern, strinput, start_from = 0, found_location = 0): if len(strinput) == 0: return found_location if len(pattern) == 0: return -1 for i in iter(pattern): start_from += 1 for j in iter(strinput): if i == j: found_location += start_from - 1 return brute_force(pattern[start_from:], strinput[1:], 0, found_location) else: break return -1 def test_beginword(self): self.assertEqual(0, searchstring.brute_force("Hello how are you?", "Hello")) def test_endword(self): self.assertEqual(14, searchstring.brute_force("Hello how are you?", "you?")) def test_singlechar(self): self.assertEqual(4, searchstring.brute_force("Hello how are you?", "o")) def test_emptystring(self): self.assertEqual(0, searchstring.brute_force("Hello how are you?", "")) def test_emptypattern(self): self.assertEqual(-1, searchstring.brute_force("", "how"))