hafy

由于多次交換郵票沒有滿足所有人的需求，小Z被趕出了集郵部。無處可去的小Z決定加入音樂部，為了讓音樂部的人注意到自己的才華，小Z想寫一首曲子。為了讓自己的曲子更好聽，小Z找到了一些好聽曲子作為模板。曲譜可以表示成只包含小寫字母的字符串，小Z希望自己最終的曲譜中任意一個長度為K的子串都是一個模板的子串。現(xiàn)在小Z想知道自己的曲譜最長可以是多長，如果可以無限長的話請輸出INF。

forget

對于30%的數(shù)據(jù)：K=2。 對于70%的數(shù)據(jù)：每組數(shù)據(jù)字符串總長不超過1000。 對于100%的數(shù)據(jù)：每組數(shù)據(jù)字符串總長不超過100000，1≤K≤100000。每個測試點數(shù)據(jù)不超過10組。

anfa

刨根問底： 這道題究竟在求些什么？ 在即將要求的曲譜中，我們希望它的所有長度為k$k$子串都必須是一個模板的子串。 出于我必須明白這個曲譜究竟會有什么樣的性質(zhì)這個目的，我倒過來思考。

曲譜它的每個長度為k$k$的子串都并非獨立而言的； 對于一個長度為k?1$k-1$的子串，如果能夠后接字符，就等同于在某個包含這個子串的模板中的后接字符。 如果我要解題，肯定是在這個特殊之處做手腳。

這個特殊之處給我們什么啟發(fā)呢？ 挖掘：

這樣就好做了，一個哈希套上去就是了。