Open CTP314 opened 5 years ago
https://ctp314.github.io/2019/07/05/HEOI2015-%E6%9C%80%E7%9F%AD%E4%B8%8D%E5%85%AC%E5%85%B1%E5%AD%90%E4%B8%B2/
P4112 [HEOI2015]最短不公共子串 求两个字符串最短不公共子序列和子串 我们需要两个自动机，一个可以接受所有子串，另一个可以接受所有子序列，前者我们可以使用 $SAM$，后者我们要构造一个叫做序列自动机的东西 序列自动机的构造不难理解，记录每个字符上一个出现位置，连转移边即可，构造复杂度为 $O(n|S|)$，感性理解下就是每一次加入的复杂度等价为从这一次加入到上一加入之间有多少字符
https://ctp314.github.io/2019/07/05/HEOI2015-%E6%9C%80%E7%9F%AD%E4%B8%8D%E5%85%AC%E5%85%B1%E5%AD%90%E4%B8%B2/
P4112 [HEOI2015]最短不公共子串 求两个字符串最短不公共子序列和子串 我们需要两个自动机，一个可以接受所有子串，另一个可以接受所有子序列，前者我们可以使用 $SAM$，后者我们要构造一个叫做序列自动机的东西 序列自动机的构造不难理解，记录每个字符上一个出现位置，连转移边即可，构造复杂度为 $O(n|S|)$，感性理解下就是每一次加入的复杂度等价为从这一次加入到上一加入之间有多少字符