## 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.

Pages: 1 2

### 11 Responses to “String Search: Brute Force”

1. […] Praxis – Brute Force By Remco Niemeijer Today’s Programming Praxis post is another easy one. We have to implement a brute-force string search. […]

2. Remco Niemeijer said

```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
```
3. Connochaetes said

> we use a Scheme idiom to conflate the two loops into a single loop.

Could you please explain for non-Schemers? Looks interesting.

4. programmingpraxis said

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.

5. Connochaetes said

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
end
```

And 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]

6. Connochaetes said

Thanks for explaining the named let idiom!

7. iama said

I posted it too soon before reading the ‘How to post source code’ document.

static int BruteForceStringSearch(string strInput, string strSearch)
{
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]

8. Matt said

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

9. 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]

10. Vikas Tandi said

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;
}
```
11. 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"))

```