TopCoder

Thumb qz2vnqoblj6vp6q
miku
https://chino.taipei

User's AC Ratio

33.3% (1/3)

Submission's AC Ratio

4.5% (1/22)

Tags

Description

好不容易躲過晨莉的攻擊,暫時得以喘氣的你

決定無論如何,先蓋一間小屋再說

沒想到一日,門外傳來了敲門聲……
你以為是晨莉來了,挫的要死,
但你決定雖然你,もも,是一個弱雞勇者,還是應當去應一下門
沒想到門外打開是……

你滿懷興奮的問了她的名字,
沒想到這隻苦力怕娘搖了搖頭:
「你要先陪我玩一個遊戲我才要告訴你我的名字。」

「原來還會傲嬌啊」你,もも,一個弱雞勇者興奮了一下。
「好啊那我們要玩什麼遊戲?」
「我們來玩神秘的斯特林遊戲」

在講遊戲規則前先來講一個東西叫做"環狀相等"
一個字串A若跟B環狀相等則代表
將A拆成兩個子字串(可以是空字串)然後交歡兩個位置在接起來而且這個新的字串跟B一樣
例如:abbaab 跟 ababba環狀相等(abbaab -> (abba, ab) -> ababba)

接下來是斯特林遊戲的規則了
給你一個由小寫英文字母組成長度為N的字串T
找出該字串的前綴(包含開頭的子字串或空字串)P跟後綴(包含結尾的子字串跟空字串)S並且
1.P跟S環狀相等
2.P跟S的長度<N/2
3.P跟S最長

請告訴苦力怕P的長度

Input Format

有多筆輸入,讀到EOF結束
對於每筆測資,
第一行輸入正整數N代表字串長度
第二行輸入字串T

30%的測資N≤500
50%的測資N≤5000
100%的測資N≤1000000

Output Format

每筆測資,輸出一個正整數X代表答案

Sample Input

15
ababbabababbaab

Sample Output

6

Hints

遊戲結束之後,你,もも,一個弱雞勇者,得知了苦力怕娘的名字叫做筱苞

Problem Source

Step5

Subtasks

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

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