substring search

[djassie78]

Hi All,
I need an efficient algorithm for this trouble. I need a function f(A,B) which says if string B is contained in string A. The characters of string B only need to be in the right order, like in this example

A = 1 2 3 4 5 6 7 8 9
B = 2 5 9

in this example find(A,B) should say B is contained in A. Does anyone knows an efficient algorithm to do that? Thanks,

[marceln]

Here's a list of string matching algorithms: http://en.wikipedia.org/wiki/String_searching_algorithm.
The Boyer-Moore algorithm is the most common.

[CMPITG]

What you are looking for is sequences matching, not string!!!
This can be done by removing redundant items of A (which are not contained in B), then replace the remain with the order of theirs in B and find the longest increasing subsequence.
Correct me if I'm wrong ^_^

[pm_kirkham]

in this example find(A,B) should say B is contained in A.The standard algorithm for this (well, for set inclusion using sorted list representation) is to iterate over A looking for each element in B in turn, so is O(length(A)). That assumes that A =1 2 2 5 5 5 9 is also valid if it finds _ 2 _ 5 _ _ 9 (some things which want what you're asking don't want repetitions).