0
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Have a look and string matching automata and algorithms. You'll note that you can easily modify many of them for matching prefixes. $\endgroup$
    – Raphael ♦
    Oct 22, 2017 at 16:56

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.