hafy

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

forget

對(duì)于30%的數(shù)據(jù)：K=2。 對(duì)于70%的數(shù)據(jù)：每組數(shù)據(jù)字符串總長(zhǎng)不超過(guò)1000。 對(duì)于100%的數(shù)據(jù)：每組數(shù)據(jù)字符串總長(zhǎng)不超過(guò)100000，1≤K≤100000。每個(gè)測(cè)試點(diǎn)數(shù)據(jù)不超過(guò)10組。

anfa

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

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

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

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