UVa 10298

From Algorithmist
Jump to navigation Jump to search

10298 - Power Strings[edit]

Summary[edit]

We are given a string. Can we find a substring which is repeated n times and will equal the original string ? Find the largest value of n.

Explanation[edit]

The original string can have a length, call it len, of up to 1,000,000 characters. n must be a divisor len. We can check i from 1 to sqrt(len) to see if the number will divide into len with no remainder. If i is a factor of len, add i and len / i to a vector. The size of this vector will never exceed 250. Now sort the vector. Start at at largest value in the vector and see if the first n chars of the string form a substring which repeats len / n times.

Gotchas[edit]

None

Notes[edit]

1. There are five different numbers with 240 factors: 720720, 831600, 942480, 982800 and 997920. No other number less than or equal to one million has more factors. 2. This problem is similiar to UVA 455 Periodic Strings