1877 . 破：萌娘苦力怕
TopCoder
Tags
Description
好不容易躲過晨莉的攻擊，暫時得以喘氣的你
決定無論如何，先蓋一間小屋再說
沒想到一日，門外傳來了敲門聲……
你以為是晨莉來了，挫的要死，
但你決定雖然你，もも，是一個弱雞勇者，還是應當去應一下門
沒想到門外打開是……
你滿懷興奮的問了她的名字，
沒想到這隻苦力怕娘搖了搖頭：
「你要先陪我玩一個遊戲我才要告訴你我的名字。」
「原來還會傲嬌啊」你，もも，一個弱雞勇者興奮了一下。
「好啊那我們要玩什麼遊戲？」
「我們來玩神秘的斯特林遊戲」
在講遊戲規則前先來講一個東西叫做"環狀相等"
一個字串A若跟B環狀相等則代表
將A拆成兩個子字串(可以是空字串)然後交歡兩個位置在接起來而且這個新的字串跟B一樣
例如:abbaab 跟 ababba環狀相等(abbaab -> (abba, ab) -> ababba)
接下來是斯特林遊戲的規則了
給你一個由小寫英文字母組成長度為N的字串T
找出該字串的前綴(包含開頭的子字串或空字串)P跟後綴(包含結尾的子字串跟空字串)S並且
1.P跟S環狀相等
2.P跟S的長度 $\leq N/2$
3.P跟S最長
請告訴苦力怕P的長度
Input Format
有多筆輸入，讀到EOF結束
對於每筆測資，
第一行輸入正整數N代表字串長度
第二行輸入字串$S$
對於所有測資，$N\leq 10^ 6, T\leq 20$。
Output Format
每筆測資，輸出一個正整數X代表答案
Sample Input 1
15
ababbabababbaab
ababbabababbaab
Sample Output 1
6
Hints
遊戲結束之後，你，もも，一個弱雞勇者，得知了苦力怕娘的名字叫做筱苞
Problem Source
Step5
2022/08/01 測資修正 by Yihda Yol
2023/11/16 Format敘述微調 by oToToT
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | $N\leq 500$ | 30 |
| 2 | 0~3 | $N\leq 5000$ | 20 |
| 3 | 0~5 | 無額外限制 | 50 |