# Fastest way to check if prefix of small string is substring of big string

Let's say we have given 2 strings $A, B$, and let's suppose that the size of $A$ is pretty small (100 characters) and the size of $B$ is pretty big (1 million).

We define prefix of string $S$ as string $Y$ that contains the first $x$ letters (size of prefix always is less than or equal to size of whole string).

And the problem is to check for all prefixes of $A$, they are not too many if they are substrings of string $B$.

It is pretty slow if for each prefix we are traversing the whole string, is it possible to do something faster, maybe using string hasing?

• Have a look and string matching automata and algorithms. You'll note that you can easily modify many of them for matching prefixes. – Raphael Oct 22 '17 at 16:56

## 1 Answer

Why would you need to traverse the big string for each prefix? Let's say A = "Some short string". So you traverse string B, looking for the letter "S". If not found, then no prefix of A is contained in B. If found, you found the prefix "S", and start at that point searching for "So". And so on.