On 07/08/12 12:28, (Ted Harding) wrote:
Well, that certainly simplifies matters! However, on the general question (and assuming that you're satisfied with just picking up the first match, i.e. knowing that there's at least one match), then the only fool-proof general method I can think of is the following. It presumes that you have enough RAM for two copies of the target string, plus whatever is needed for the program etc.
Obviously the target has to be stored somewhere, but this needn't be in RAM (I'm assuming that there's "plenty" of ROM space from the way Chris described the problem).
If so, you start with an integer index into the target set to zero, and when you find a character in the stream that matches the character pointed to by the index you increment the index. When you get to the end of the target string you have you match.
The trick is how to replay things when you get a miss midway into the target, but that's not actually that hard; you loop through the data from the second character in the target to the current (failed) position replaying them as if they came from the stream, retesting them as you go.
From a quick play the hardest bit seems to be coming up with test cases that pick up the edge cases. I can't find any particularly "difficult" examples but also can't prove they aren't out there.