String Search: Brute Force
August 21, 2009
Our solution simply loops through the pattern and the string, resetting at each mis-match, until it reaches the end of the pattern, when it reports a match, or the end of the string, when it reports a failure:
(define (bf-search pat str . s)
(let ((plen (string-length pat)) (slen (string-length str)))
(let loop ((p 0) (s (if (null? s) 0 (car s))))
(cond ((= p plen) (- s plen))
((= s slen) #f)
((char=? (string-ref pat p) (string-ref str s))
(loop (+ p 1) (+ s 1)))
(else (loop 0 (- s p -1)))))))
In many languages, the loop on p would be nested inside the loop on s; we use a Scheme idiom to conflate the two loops into a single loop. Scheme strings are indexed from zero; some languages index from one, so the above code may require adjustment.
Our test suite uses the assert macro from the Standard Prelude; remember that, with assert, “No news is good news:”
(define (test-search search)
(assert (search "Programming Praxis" "Programming Praxis") 0)
(assert (search "Praxis" "Programming Praxis") 12)
(assert (search "Prax" "Programming Praxis") 12)
(assert (search "praxis" "Programming Praxis") #f)
(assert (search "P" "Programming Praxis") 0)
(assert (search "P" "Programming Praxis" 5) 12)
)
You can run this code at http://programmingpraxis.codepad.org/XanMzASO.
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"))