TopCoder

Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

42.9% (3/7)

Submission's AC Ratio

25.9% (14/54)

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

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1 2 3
1 1000 65536 65536 1 2 3
2 1000 65536 65536 2 3
3 1000 65536 65536 2 3
4 1000 65536 65536 3
5 1000 65536 65536 3