骨骼 熱呼呼的掛經

Johnese 发表于 2018-10-4 13:58
复制的时候可以插在中间吗？比如A是acb B是abc 是两次还是三次呢？

這我沒問到,但依我的理解應該是要照順序的插入

daisy35 发表于 2018-9-29 10:56
请问能share一下mlogn的思路么？

感觉应该是用一个map把t的所有字符和位置的list存储一下，然后用dfs解决

这个题厉害了。。。没看懂题。

先预处理B,把所有子串存到hashmap里，O(N^2)
然后动态规划， f[i] 代表前i个字母最少需要几次，f[i] = min(f[j])+1,  B[j~i] 在hashmap 里， O(N^2)
总O(N^2)，不知道有没有更优解法

我的想法是 A从最大子串开始逐步缩小，然后用recursion来match右边剩下的子串，感觉应该可以优化成dp？

请问用B的子串构建A的时候，必须从A的开头位置开始吗
求楼主给下具体思路

我觉得two pointers idxA， idxB 就可以了，一个扫strA， 一个扫strB。idxB的数值是可以无限增加的，想要知道在strB中指的是哪个char只要 strB.charAt(idxB % nB), nB是strB的长度， 直到把strA中所有的char都找完，返回 idxB/nB + 1 即可