To solve this problem, we need to find the shortest substring that repeats to form the entire given string. If no such substring exists, we return the original string.
Approach
- Understand the Problem: We need to find the smallest length
ksuch that the string can be divided intomequal parts (wherem = length of string / k), and all parts are identical. - Check Divrs: For each possible
kfrom 1 to half the length of the string (sincekmust be a divr of the string length to form equal parts):- If
kdivides the string length, check if repeating the substring of lengthk(starting from the beginning)mtimes equals the original string.
- If
- Return Result: If such a
kis found, return the substring of lengthk. If no suchkexists, return the original string.
Solution Code
def shortest_repeating_substring(s):
n = len(s)
for k in range(1, n // 2 + 1):
if n % k != 0:
continue
substring = s[:k]
if substring * (n // k) == s:
return substring
return s
# Example usage:
print(shortest_repeating_substring("abcabcabc")) # Output: "abc"
print(shortest_repeating_substring("ababab")) # Output: "ab"
print(shortest_repeating_substring("abcd")) # Output: "abcd"
Explanation
- Divr Check: For each
k(from 1 to half the string length), we first check ifkdivides the string length. This ensures that the string can be split into equal parts of lengthk. - Repeating Substring Check: For valid
k, we take the substring of lengthkfrom the start of the string and repeat itmtimes (wherem = n/k). If this repeated substring equals the original string, we return it immediately (since we are checking from the smallestkfirst). - Edge Cases: If the string length is 1, the loop doesn't run, so we return the original string. For non-repeating strings (like "abcd"), no valid
kis found, so we return the original string.
This approach efficiently finds the shortest repeating substring with a time complexity of O(n*d), where d is the number of divrs of the string length. This is optimal for most practical cases.


作者声明:本文包含人工智能生成内容。