How to find repeating sequence of characters in a given array?

Question

My problem is to find the repeating sequence of characters in the given array. simply, to identify the pattern in which the characters are appearing.

   .---.---.---.---.---.---.---.---.---.---.---.---.---.---. 1: | J | A | M | E | S | O | N | J | A | M | E | S | O | N |    '---'---'---'---'---'---'---'---'---'---'---'---'---'---'

   .---.---.---.---.---.---.---.---.---.---.---.---.---.---.---. 2: | R | O | N | R | O | N | R | O | N | R | O | N | R | O | N |    '---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'

   .---.---.---.---.---.---.---.---.---.---.---.---. 3: | S | H | A | M | I | L | S | H | A | M | I | L |    '---'---'---'---'---'---'---'---'---'---'---'---'

   .---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---. 4: | C | A | R | P | E | N | T | E | R | C | A | R | P | E | N | T | E | R |    '---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'

---

Example

Given the previous data, the result should be:

1. "JAMESON"
2. "RON"
3. "SHAMIL"
4. "CARPENTER"

---

Question

• How to deal with this problem efficiently?

Answer 1

Tongue-in-cheek O(NlogN) solution

Perform an FFT on your string (treating characters as numeric values). Every peak in the resulting graph corresponds to a substring periodicity.