Author |
Topic: String matching (Read 1339 times) |
|
witee
Newbie
Posts: 48
|
 |
String matching
« on: Aug 16th, 2010, 1:14pm » |
 Quote  Modify
|
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’)
|
|
 IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender: 
Posts: 1001
|
|
Re: String matching
« Reply #1 on: Aug 17th, 2010, 4:56am » |
Quote Modify
|
One can use a slightly modified version of Bitap Algorithm.
-- AI
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
solid
Newbie
Posts: 5
|
|
Re: String matching
« Reply #2 on: Sep 4th, 2011, 3:56pm » |
Quote Modify
|
1) Suffix Tree
2) Robin Karp
3) Brute Force
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print