[2021.1.31多校省選模擬12]隨機變換的子串

對于這三種操作，我們驚奇地發現有這樣的性質，所有長度大于4的字符串都可以通過變換變為長度小于等于4的字符串，那么查詢本質不同的字符串我們只需要處理12種字符串的出現次數即可。

然后對于區間所有字符串數量級是$O(n^2)$的，所以我們考慮分治處理，那么將分治用一個數據結構維護下來，那就是一顆線段樹了，然后考慮需要哪些信息，我們需要維護所有前綴信息和后綴信息以及整個串信息。

考慮如何快速合并信息，這個思想就很巧妙了，就是對這12個串建立一個類似于自動機的東西，然后每一條邊代表增加一個字符a或者b，然后到達指定狀態，然后由于數據范圍很小所以我們可以手動模擬出來這個圖，那么合并只需要再圖上走不超過4步就好了。

總結

以上是生活随笔為你收集整理的[2021.1.31多校省选模拟12]随机变换的子串(线段树维护分治/字符串/自动机思想）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。