T3

賽時近 \(2h\)，賽后 \(1h\)。

洛谷 P14363

題意

看題面吧，值得說一下的是替換只能由至多一次，否則沒法做了。

另外 $|t_1| \ne |t_2| $ 的情況是可能存在的，可能需特判，輸出 \(0\)（純出題人沒事干。）

思路

講一個自己想得做法。

令 \(len_i = |s_i|\)， 假設(shè)我們把 \(t_1[r - len_i + 1, r]\) 替換位 \(s_1\)。替換后為 \(t_2\) 的充要條件是：

• \(lcp \ge r - len_i + 1\)
• \(lcs \ge |t_i| - r\)。
• \(s1 = t_1[r - len_i + 1, r]\)。
• \(s_2 = t_2[r - len_i + 1, r]\)。

可以枚舉 \(r\)，第一個條件化為 \(len_i \ge x\)。然后后面兩個條件是一個多串匹配問題，使用 AC 自動機建出 fail 樹后就是一個 dfs 序在一個區(qū)間里。是一個三維偏序，使用 cdq 分治可以達到 \(O(S \log^2 S)\)。

賽時想到這就卡住了，所以應(yīng)該只有 \(60pts\)。（希望 CCF 機子好）

優(yōu)化需要用到一個小 trick?？梢詫?\(s_1, s_2\) 插到一起（\(s1_0, s2_0, s1_1, s2_1, \dots\)），\(t_1, t_2\) 同理。這樣后面兩個條件就縮減成了一個，就是套路二維數(shù)點了。因為相對位置不變，所以是正確的。

時間復(fù)雜度 \(O(S \log S)\)。洛谷民間數(shù)據(jù) \(1.4s\)。

賽時沒有想到可以把 \(s1, s2\) 插到一起，所以是一個三維偏序。插到一起后少了一個條件就可以單 \(\log\) 做了。

還有 AC 自動機不要把 \(t_1,t_2\) 也插進去，只需要在 trie 上跑一次就行了，多了兩倍常數(shù)，呃呃呃。

CCF 多久沒考字符串呀？？？這個 trick 好久沒用到了。