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.

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 644 other followers

%d bloggers like this: