Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Assume a stream of characters$(c)$ where $ c \in (A, B, C ... Z)$.

I need to identify patterns available in the stream. As per the definition of a pattern I should be looking for a recurring string.

For example if the stream observed thus far is:

$$A\space B\space A\space S\space Y\space K\space I\space A\space B\space L\space J\space L\space B\space C\space L\space K\space I\space P\space I\space B\space C\space A\space B\space A\space B\space A\space B\space A\space B\space $$

By observation it can be observed that the string $AB$ appears 6 times whilst $BC$ appears 2 times.

My questions are as follows:

  1. Apart from repetition are there any conditions that a string should suffice in order to be considered a pattern
  2. If repetition is the only factor how many times a string should appear on the stream to be legitimately considered a pattern? Is there any mathematical logic in deciding this factor. (As per my understanding it has to be at least 2 since a single character itself could not be considered a pattern in this case. A single character could also be a pattern if it appears in a fixed interval however, I'm only focused on the string make up at this point.)
share|cite|improve this question

1.) In your given string $AB$ and $BC$ are repeating substrings, not patterns. A pattern in a sequence would be a repeating substring that occurs every $n$ characters, where $n \in \{0, 1, 2, \ldots, n\}$. In your given string $AB$ appears after 5 characters, then after 13 characters, then after $0$ characters (3 times); which is not a pattern. However if you were given the string

$$ A \, B \, D \, L \, N \, A \, B \, R \, O \, D \, A \, B \ $$

$AB$ appears every 3 characters, making that a pattern.

2.) Given my answer to your first question the answer to this question should be pretty straight forward. Just incase: A substring cannot be considered a pattern unless it is repeated every $n$ characters, where $n \in \{0, 1, 2, \ldots, n\}$. If there is no repetition based on this rule the substring is not a pattern.

I hope this helps! Also, if anyone can expand on this or edit it in anyways please do so.

share|cite|improve this answer
Wow answered after 1 year :D However, I think if AB repeats multiple times in a string without the gap it has to be some kind of a pattern too. – Synex Nov 2 '14 at 11:24
If you have a string $A \, B \, A \, B \, ...$ then yes, the pattern is $A \, B$. However, if you had $\,A \, B \, A \, B \, D \, P \, O \, A \, B \, Q$ then $A \, B $ would not be a pattern – steveclark Nov 2 '14 at 18:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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