wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> String matching
        
(Message started by: witee on Aug 16^th, 2010, 1:14pm)

Title: String matching
Post by witee on Aug 16^th, 2010, 1:14pm

Find if a string is a substring of another. Note that a mismatch of one character
should be ignored. A mismatch is either an extra character (’dog’ matches ‘xxxdoogyyyy’), a
missing char (’dog’ matches ‘xxxxdgyyyy’) or a different character (’dog’ matches ‘xxxdigyyyy’)

Title: Re: String matching
Post by TenaliRaman on Aug 17^th, 2010, 4:56am

One can use a slightly modified version of Bitap Algorithm (http://en.wikipedia.org/wiki/Bitap_algorithm).

-- AI

Title: Re: String matching
Post by solid on Sep 4^th, 2011, 3:56pm

1) Suffix Tree
2) Robin Karp
3) Brute Force