妮可妮可妮

【問題描述】

小 P 特别喜歡動畫 Love Live 中的角色妮可,每當他聽到妮可說“niconiconi”

時,他總會感到特别興奮,還會露出紳士般的微笑。

作為一名理論計算機科學家,小 P 開始研究“niconiconi”這種串的特點。

他發現,“niconiconi”可以拆成“ni”、“co”、“ni”、“co”、“ni”這

五部分。

對這個模型進行了抽象後,小 P 發現,任何形如 ABABA 的串都有類似的特點,

其中 A、B 為非空串,我們稱這樣的串滿足性質 P。比如“aaaaa”就滿足性質 P,

而“ababab”卻不滿足性質 P。

有了這個革命性的發現,結合他最近新學的資料結構“字尾樹”,小 P 決定

造一道題。這道題是這樣的,小 P 給你一個僅由小寫英文字母組成的串 S,你拿

到這個串之後,小 P 會問你 q 個問題,每個問題形如“S 的字尾 p 是不是滿足性

質 P 的串呀”。

注:設 S 的長度為 n,那麼 S[1..n]的字尾 p 就是子串 S[p..n]。

【輸入】

輸入檔案名:nico.in

第一行一個僅由小寫英文字母組成的串 S。

第二行一個整數 q。

接下來 q 行,每行一個數 p_i,表示第 i 次的問題是:“S 的字尾 p_i 是不

是滿足性質 P 的串呀”。

【輸出】

輸出檔案名:nico.out

輸出檔案一共 q 行,第 i 行為對第 i 個問題的回答。

如果滿足性質 P,回答:“niconiconi”。(不包含引号)

如果不滿足性質 P,回答:“no”。(不包含引号)

【資料範圍】

測試點 1..3:|S|≤100

測試點 1..6:|S|≤1000

測 試 點

1..10 : 1 ≤ |S| ≤ 5*10 5 , 1 ≤ q ≤ 10 5

形如ABABA的串，可以化為(端點)A(斷點2)[BA(2)](斷點1)[BA(1)]

我們令f[i]為1～i與1～n 的最長公共字尾

枚舉斷點1為i

[BA(1)]=str[i~n]

[BA(2)]=str[j~i-1]   (n-i+1=i-j)

則端點的範圍為j-min(g[j-1],n-i)

則j-min(g[j-1],n-i)~~j-1的字尾顯然都符合ABABA

那麼有幾個問題：

1.怎麽求出f[i]，用二分，二分長度并比對，比對失敗則縮小長度

2.怎麽快速判斷字元串相同，用字元串hash

3.j-min(g[j-1],n-i)~~j-1用差分數組全部+1，就可以O(1)查詢