EmbLogic's Blog

q-WAP to find the no of times that a given word(i.e a short string) occurs in a string (i.e a long string!)………..how we can start this programe…………

5 Responses to

  1. There are various ways of string matching …
    one of them is (which i implemented in my program) :

    e.g. “the algorithm of the program is here”
    suppose we have to find number of occurences of “the”
    1.match the char of “the” with the first char of entered string
    ‘t’ matches
    2. if it matches den match the second char

  2. 3. in case it doesnt then match the first char of short string with second char of string ..
    nd whenever the total no of consecutive matches is equal to the length of short string.you have got a match . juhst to give u an idea :

    E.g long string : “i am a programmer”
    e.g. short string : “programmer”

    now match the first char
    i am a programmer
    |
    p

    doesnt matches move to the right in long string

    i am a programmer
    |
    p

    doesnt match move right

    keep moving till ur first char of short string matches
    u’ll reach a stage like this

    i am a programmer
    |
    p matched character = 1

    i am a programmer
    ||
    pr matched character = 2

    i am a programmer
    |||
    pro matched character =3

    similarly

    i am a programmer
    ||||||||||
    programmer
    matched character = 10 =length of the short string . now you have got ur first short string in the long string .. which is the only one in this case .. keep shifting throughout the length of the short string or to optimize your program you can shift till

    (length of the long string – length of the short string)

    Note:there are other string matching algorithms as well .. u might have studied it in Design and analysis of algorithm if you are a CSE student .

    :) keep commenting if you find any problem .

  3. the example posted on the above comment includes white spaces which were compressed after posting .. so dont go through it

  4. Abhishek says:

    there is also a predefined function “strstr” defined in string.h

  5. kpeswani says:

    since u r developing an algo try to reduce the complexity of ur algo…..in O(n)

    Hint: study data structure TRIE

Leave a Reply to kpeswani Cancel reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>