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.

About these ads

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

    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
    
  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
    
  6. Connochaetes said

    Thanks for explaining the named let idiom!

  7. iama said

    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);
    
    
  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))
    ))
    
  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"))
    
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 628 other followers

%d bloggers like this: