Advertisement
Time limit2sMemory limit128 MB
Given the L characters currently visible on a scrolling sign showing an infinitely repeated text, find the minimum possible length of the original advertisement text.
- Level
Medium5 of 10
- Topics
- String matching, String
- Solved
- No attempts yet
Problem
An electronic sign continuously scrolls one advertisement text repeated without end. The size L of the sign is the number of characters visible at one moment, so exactly L characters are shown at a time.
Let N be the length of the actual advertisement text. The advertiser repeats this length-N text forever and scrolls it across the sign. For example, if the text is aaba and L=6, the sign may show aabaaa at one moment, then abaaab one second later, then baaaba after that as the text shifts by one character.
You are given the length-L string visible when Sejun looked at the sign. Find the shortest possible length of an advertisement text that could produce this string.
Input
The first line contains the size L of the sign. The second line contains the length-L string currently visible on the sign.
Output
Print the minimum possible length of the advertisement text.
Constraints
- 1 <= L <= 1,000,000
- The visible string consists only of lowercase English letters.