找到相差只有一个字符的string

mgccl 发表于 2019-3-5 18:33
1. 目标是worst case O(MN)的啊. 建立trie没有问题. trie只建立了一次.

2. 实际上我们需要的信息不是t ...

建立正反trie怎么确定正反中的两个分支是来自同一个字符串的,这个问题没有解决啊

mgccl 发表于 2019-3-5 18:33
1. 目标是worst case O(MN)的啊. 建立trie没有问题. trie只建立了一次.

2. 实际上我们需要的信息不是t ...

一开始我就想到了正反trie,但是即使正的trie有两个是同一个sufix,反的也有两个是同一个suffix,但是并不能说明他们就是来自两个字符串,也可能是多个,想要知道是来自两个字符串的话,trie的节点就要记录字符串的来源,那么比较在最坏的情况下又是o(m)的,所以最坏还是o(nmm)

这题就是两循环，外循环从字串位置0到m，内循环遍历所以字串，改掉一个位置，然后放到SET里，如果有重复就得解。