F. 地圖壓縮 題解(kmp 最小循環節)

其實就是發現行和列不影響然後就可以求了

官方題解如下

不難發現行與列是兩個獨立的問題，是以隻需要求出行的最短循環節的長度，再求出列的

最短循環節的長度，相乘就是答案。

以行為例，首先通過 Hash 将問題轉化為一維問題。一維問題則是經典問題，對于一個長

度為 n 的字元串，長度為 d 的字首是循環節當且僅當長度為 n − d 的前字尾相等，是以需要找

到這個字元串最長的字首，滿足該字首也是該字元串的字尾。可以枚舉所有可能的 d 然後使用

Hash O(1) 判斷；也可以使用 KMP 算法求出 nxt 數組，答案即為 n − nxt[n]。

時間複雜度 O(n2 + qn)。

不擺爛了，寫題