Finding Periods

Problem Overview

Learning Goals

After solving this problem, you will be able to:

• Understand the mathematical relationship between periods and borders
• Implement the KMP failure function for period detection
• Apply the formula: period = length - border to find all periods
• Recognize when a string has a “complete” period vs partial repetition

Problem Statement

Problem: Given a string of length n, find all period lengths of the string. A period is a prefix that can be repeated to form the string (with possibly a partial repetition at the end).

Input:

• Line 1: A string of n lowercase letters

Output:

• All period lengths in increasing order (space-separated)

Constraints:

• 1 <= n <= 10^6
• String contains only lowercase English letters (a-z)

Example

Input:
abcabca

Output:
3 6 7

Explanation:

• Period 3: “abc” repeated gives “abc

  abc

  a” which matches “abcabca”

• Period 6: “abcabc” repeated gives “abcabc

  a” which matches “abcabca”

• Period 7: The full string is always a period of itself

Intuition: How to Think About This Problem

Pattern Recognition

Key Question: How do periods relate to the KMP failure function (borders)?

The crucial insight is: Period = Length - Border

A border of a string is a proper prefix that is also a suffix. If a string has a border of length b, then the string can be generated by repeating a pattern of length n - b.

Breaking Down the Problem

1. What are we looking for? All lengths p such that repeating s[0..p-1] generates s
2. What information do we have? The failure function gives us all borders
3. What’s the relationship? If b is a border, then n - b is a period

The Period-Border Relationship

String: a b c a b c a
        |--border--|
        a b c a

Border length = 4
Period = 7 - 4 = 3

Verification: "abc" repeated = "abc|abc|a" = "abcabca"

Why Does This Work?

If the first b characters equal the last b characters (border definition), then:

• Characters at positions [0, n-b-1] equal characters at positions [n-b, n-1] - (b positions)
• This means shifting by (n-b) maps matching characters
• Therefore, (n-b) is a valid period

Finding ALL Periods

The failure function at position n-1 gives the longest border. But we need all borders to find all periods.

Key insight: Borders are nested! If b is a border, then all borders of the prefix s[0..b-1] are also borders of the original string.

String: aabaabaa (length 8)
lps[7] = 5  -> border "aabaa" -> period 3
lps[4] = 2  -> border "aa"    -> period 6
lps[1] = 1  -> border "a"     -> period 7
lps[0] = 0  -> no more borders -> period 8 (full string)

Solution 1: Brute Force

Idea

For each candidate period p from 1 to n, verify if repeating the prefix of length p generates the string.

Algorithm

1. For each p from 1 to n:
2. Check if s[i] == s[i % p] for all positions i
3. If all match, p is a valid period

Code

def find_periods_brute_force(s: str) -> list[int]:
  """
  Brute force: check each candidate period.

  Time: O(n^2) - for each of n periods, check up to n characters
  Space: O(1) - excluding output
  """
  n = len(s)
  periods = []

  for p in range(1, n + 1):
    is_period = True
    for i in range(n):
      if s[i] != s[i % p]:
        is_period = False
        break
    if is_period:
      periods.append(p)

  return periods

Complexity

Why This Works (But Is Slow)

Correctness is guaranteed because we check every position against the period pattern. However, checking each period independently wastes work - we recompute information that could be shared.

Solution 2: Optimal Solution using KMP Failure Function

Key Insight

The Trick: Use the KMP failure function to find all borders, then convert each border to a period using: period = length - border

Failure Function Definition

In plain English: lps[i] tells us “how much of the beginning of the string also appears at the end of s[0..i]”

Algorithm

1. Build the KMP failure function (lps array)
2. Start with the longest border: border = lps[n-1]
3. Convert to period: period = n - border
4. Follow the border chain: next border = lps[border - 1]
5. Repeat until border = 0, then add n itself as a period
6. Reverse to get periods in increasing order

Dry Run Example

Let’s trace through with input s = "abcabca":

Step 1: Build failure function (lps array)

  String: a b c a b c a
  Index:  0 1 2 3 4 5 6

  i=0: lps[0] = 0 (by definition)

  i=1: s[1]='b' vs s[0]='a' -> mismatch, lps[1] = 0

  i=2: s[2]='c' vs s[0]='a' -> mismatch, lps[2] = 0

  i=3: s[3]='a' vs s[0]='a' -> match!, lps[3] = 1

  i=4: s[4]='b' vs s[1]='b' -> match!, lps[4] = 2

  i=5: s[5]='c' vs s[2]='c' -> match!, lps[5] = 3

  i=6: s[6]='a' vs s[3]='a' -> match!, lps[6] = 4

  Final lps: [0, 0, 0, 1, 2, 3, 4]

Step 2: Find all periods by following border chain

  n = 7

  border = lps[6] = 4
    period = 7 - 4 = 3     -> add 3

  border = lps[3] = 1
    period = 7 - 1 = 6     -> add 6

  border = lps[0] = 0
    period = 7 - 0 = 7     -> add 7

  border = 0, stop

  Periods collected (in reverse): [3, 6, 7]

Step 3: Output in increasing order
  Result: 3 6 7

Visual Diagram

String: a b c a b c a     (length 7)
        0 1 2 3 4 5 6

Border chain visualization:

lps[6] = 4:  [a b c a] . . [a b c a]  -> period = 7-4 = 3
              prefix        suffix

lps[3] = 1:  [a] . . . . . [a]        -> period = 7-1 = 6

lps[0] = 0:  (empty border)           -> period = 7-0 = 7

Period = 3 means: "abc" repeated forms the string
  a b c | a b c | a
  -----   -----   -
  copy1   copy2   partial

Code

def find_periods_kmp(s: str) -> list[int]:
  """
  Optimal solution using KMP failure function.

  Key insight: period = length - border
  All borders form a chain via the failure function.

  Time: O(n) - building lps is O(n), following chain is O(n)
  Space: O(n) - for the lps array
  """
  n = len(s)

  # Step 1: Build KMP failure function (lps array)
  lps = [0] * n
  length = 0  # length of previous longest prefix suffix
  i = 1

  while i < n:
    if s[i] == s[length]:
      length += 1
      lps[i] = length
      i += 1
    else:
      if length != 0:
        length = lps[length - 1]  # try shorter prefix
      else:
        lps[i] = 0
        i += 1

  # Step 2: Find all periods by following the border chain
  periods = []
  border = lps[n - 1]

  while border > 0:
    periods.append(n - border)
    border = lps[border - 1]

  periods.append(n)  # full string is always a period

  # Step 3: Periods are collected in increasing order already
  return periods


def solve():
  """Main function to read input and output result."""
  s = input().strip()
  periods = find_periods_kmp(s)
  print(' '.join(map(str, periods)))


if __name__ == "__main__":
  solve()

Complexity

Common Mistakes

Mistake 1: Confusing Period with Border

# WRONG - printing borders instead of periods
border = lps[n - 1]
while border > 0:
  periods.append(border)  # This is the BORDER, not the period!
  border = lps[border - 1]

# CORRECT - convert border to period
border = lps[n - 1]
while border > 0:
  periods.append(n - border)  # period = length - border
  border = lps[border - 1]

Problem: Border and period are complementary. Border is what overlaps; period is what doesn’t. Fix: Always use period = n - border to convert.

Mistake 2: Forgetting the Full String as a Period

# WRONG - missing the full string
periods = []
border = lps[n - 1]
while border > 0:
  periods.append(n - border)
  border = lps[border - 1]
# Missing: periods.append(n)

# CORRECT
periods.append(n)  # The full string is always a valid period

Problem: Every string has itself as a period (border = 0, period = n - 0 = n). Fix: Always add n as the final period.

Mistake 3: Wrong Order in Output

# WRONG - periods collected in wrong order and not fixed
periods = []
border = lps[n - 1]
while border > 0:
  periods.append(n - border)  # collected in increasing order actually
  border = lps[border - 1]
periods.append(n)

# Note: With this implementation, periods ARE in increasing order
# because we start with longest border (smallest period)

Note: With the border chain approach starting from lps[n-1], periods are naturally collected in increasing order (longest border gives smallest period).

Mistake 4: Off-by-One in LPS Building

# WRONG - starting from i=0
for i in range(n):
  # lps[0] should be 0 by definition

# CORRECT - start from i=1
lps[0] = 0  # by definition
for i in range(1, n):
  # compute lps[i]

Edge Cases

Edge Case Analysis

All same characters (e.g., “aaaa”):

lps = [0, 1, 2, 3]
border chain: 3 -> 2 -> 1 -> 0
periods: (4-3)=1, (4-2)=2, (4-1)=3, 4
Output: 1 2 3 4

No repetition (e.g., “abcd”):

lps = [0, 0, 0, 0]
border chain: 0 (empty)
periods: 4
Output: 4

When to Use This Pattern

Use This Approach When:

• Finding all periods or the smallest period of a string
• Problems involving string repetition or cyclic patterns
• Need to check if a string is a rotation of another
• Computing pattern matching with periodicity

Don’t Use When:

• Finding periods of multiple different substrings (might need other approaches)
• Pattern matching without period requirements (standard KMP suffices)
• Problems requiring suffix-based analysis (consider suffix array/tree)

Pattern Recognition Checklist:

• Does the problem ask about “repeating” a prefix to form the string? -> Use KMP periods
• Does the problem involve string borders/overlaps? -> KMP failure function
• Is there a constraint about “minimum repetitions”? -> Period divides length check
• Need to find smallest period? -> First period in sorted output

Related Problems

Easier (Do These First)

Similar Difficulty

Harder (Do These After)

Key Takeaways

1. The Core Idea: Period = Length - Border. The KMP failure function gives us all borders through a chain.
2. Time Optimization: Instead of O(n^2) brute force, we use O(n) KMP preprocessing and O(n) border chain traversal.
3. Space Trade-off: We use O(n) space for the lps array to achieve O(n) time.
4. Pattern: This belongs to the “KMP and string periodicity” pattern family.

Practice Checklist

Before moving on, make sure you can:

• Explain why period = length - border
• Build the KMP failure function from scratch
• Trace through the border chain to find all periods
• Implement the solution in under 10 minutes
• Handle all edge cases correctly

Additional Resources

• CP-Algorithms: Prefix Function (KMP)
• CSES Problem Set - String Algorithms
• Knuth-Morris-Pratt Algorithm Visualization