## Saturday, May 21, 2011

### String pattern matching

In almost any non-trivial string application, pattern matching is an indispensable part of the code. Finding the position where the search string (pattern) exists in the source is generally referred to pattern matching. Of course, more complex pattern matching involves the use of regular expressions and other advanced techniques. There have been many algorithms that have been developed for solving this simple functionality of pattern matching. In this post, we will discuss the simplest of all: brute force search.

Brute Force Search is the simplest of all search algorithms. In this algorithm, the pattern string is searched character by character in the source string. The search begins at position 0 of the source and continues till either a match is found or the entire source string (minus the pattern string length) has been traversed.

Let’s look at the code to implement is simple brute force search technique.

`#include "stdafx.h"#include <string.h>// searches for the input pattern string in the // source string and returns either the position// where the mach is found or -1 if no match// was foundint PatternMatching(char* source, char* pattern){    // find the source and pattern lengths    int sourceLength = strlen(source);    int patternLength = strlen(pattern);    for (int pass = 0; pass <= sourceLength - patternLength; pass++)    {        // initialize the current positions        // for source and pattern                // for each pass we will have to go through the         // entire pattern string        int patCurrPos = 0;                // for each, we need to start the search at        // the current source string position        int srcCurrPos = pass;                // till we have the match, continue looping        while ((source[srcCurrPos] == pattern[patCurrPos]) && (patCurrPos < patternLength))        {            patCurrPos++;            srcCurrPos++;        }        // do we have a match        if (patCurrPos == patternLength)            return pass;    }    // match not found    return -1;}`

1. Please explain kth largest element in an array ,
largest sum of sub array ,
sum of two numbers is m then find that two numbers are present in an array or not ...
Programs too.

2. in your programme, 'while condition' should check the pattern length first. otherwise you will get index out of range exception
ex:
while ((patCurrPos < patternLength) && (source[srcCurrPos] == pattern[patCurrPos]))
{
patCurrPos++;
srcCurrPos++;
}

1. exactly what I was going to point out

3. The article you have shared here very good. This is really interesting information for me. Thanks for sharing!

4. Hi Nikhil,

Nice to be visiting your blog again, it has been months for me. Well this article that i’ve been waited for so long.

What I am having trouble with is I am trying to display a list of items from a "inventory" on a view and I want to use one of the columns to save URL's for image sources.
So far I have it to where It will display all items saved in the table, But I am having trouble pulling out the string from the imgUrl column. Can I get some help please?

In the ViewController I have an ArrayList that I haven't used yet. But I started with the idea of I will just add all the URL's to here but then I thought that if I start looping through nested lists in the view that its not going to produce what I am looking for.

Very useful article, if I run into challenges along the way, I will share them here.

MuchasGracias,
Rani

5. Your blog is great. I read a lot of interesting things from it. Thank you very much for sharing. Hope you will update more news in the future.
game for kids online