1
$\begingroup$

Suppose we have an alphabet of size $S$, a pattern of length $P$ and a text of length $T$. We want to design an algorithm for matching all caesar rotations of the pattern $P$ in the text $T$. The problem can be solved using the following two methods:

  • By $\text{KMP/Z}$ against all $S$ rotations of $P$ in time $O(P+ST)$ (we can reuse the $\text{LPS/Z}$ array of the pattern).
  • By $\text{Aho-Corasick}$ against all $S$ rotations of $P$ in time $O(SP+T)$ by preinserting all the rotations into an automaton.

Question: Can the problem be solved in $O(P+T)$ time?

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ "This can be solved:" - What can be solved? What does "this" refer to? I suggest that you edit your post to state the problem in a self-contained way: specify both the input and the desired output. You list the inputs $S,P,T$, but not the output or how it relates to the inputs. What does "solved in $P+T$" mean? Are you referring to running time? $\endgroup$
    – D.W. ♦
    Sep 18 at 5:39
  • $\begingroup$ What does "matching all rotations" mean? Do you want to output all matches for each possible rotation of $P$? Output all rotations of $P$ that have at least one match in $T$? Check whether there exists any rotation of $P$ that matches $T$? Something else? $\endgroup$
    – D.W. ♦
    Sep 18 at 21:52
  • 1
    $\begingroup$ What's the context in which you encountered this problem? If it is a practical problem you experienced, can you provide the motivation? If it is a task you saw somewhere, can you provide a reference for the source where you saw it? $\endgroup$
    – D.W. ♦
    Sep 18 at 21:54
  • 1
    $\begingroup$ @chubakuenom I think answering your own question would be educational. $\endgroup$
    – Pseudonym ♦
    Sep 19 at 0:50
  • 1
    $\begingroup$ Great. Please edit the question to incorporate that information into the question, then flag comments as 'no longer needed'. We want questions to be self-contained, so they read well and contain all necessary information for the reader, for readers who encounter this for the first time, without people having to read the comments to understand relevant context and motivation and specification of the problem statement. $\endgroup$
    – D.W. ♦
    Sep 19 at 2:04

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.