谷狗新鲜店面

stellari 发表于 2018-12-10 04:27
抱歉，我不是楼主……

如果能用来匹配的一定是str2的substring，而非subsequence的话。那只需要把上面 ...

感谢回复
最坏情况先不应该是O(n*m^3)吗
str2总共用m^2个子串 每个子串匹配O(m) 匹配完就下一个

byfwh 发表于 2018-12-10 04:49
感谢回复
最坏情况先不应该是O(n*m^3)吗
str2总共用m^2个子串 每个子串匹配O(m) 匹配完就下一个

不是，因为在已知str2[0:k]已经是一个匹配的情况下， 只用O(1)时间就可以分别知道str2[0:k+1], str2[0:k+2]...是否也为一个匹配；而在已知str2[0:k]已经不是匹配的情况下，str2[0:k+1]...就都肯定也不是匹配。也就是说，最多用O(m)时间就可以知道所有从str2的0位置开始的子串的匹配情况。

stellari 发表于 2018-12-10 05:07
不是，因为在已知str2[0:k]已经是一个匹配的情况下， 只用O(1)时间就可以分别知道str2[0:k+1], str2[0:k+ ...

不好意思 我还是不太明白 我举一个极端的例子
str1 = aaax(1000次)
str2 = xxxaaa
要匹配第一个aaa 首先str1中prefix长度取多少不确定 所以从最长开始 6 不是str2中的字串 5 不是str2中的子串 4 不是 3 是 这个过程不是O(m^3)吗 感谢回复

byfwh 发表于 2018-12-10 05:25
不好意思 我还是不太明白 我举一个极端的例子
str1 = aaax(1000次)
str2 = xxxaaa

我理解你的意思，但是我不建议你从试遍prefix长度这个思路入手。你可以找str1[i:]分别和str2[0:]，str2[1:]，……，str2[m-1:]这m个字符串的最长公共前缀（共有m个这样的公共前缀）。这m个公共前缀最长者就是str2中能找到的最长匹配。

stellari 发表于 2018-12-10 06:31
我理解你的意思，但是我不建议你从试遍prefix长度这个思路入手。你可以找str1分别和str2[0:]，str2[1:]， ...

我明白你的意思了
针对str2[i:]去和str1[i:]去找最长公共前缀 因为有O(m)个前缀 每个匹配O(m)所以O(N*M^2)
谢谢啦

但是一旦前缀match上了，就可以跳过这些已经match上的字符串，所以并非O(N) * O(M^2).
假设最坏情况，每次match一个char，每次match为O(M)的，所以总时间还是O(NM)

substring是subsequence的子集
所以subsequence能用的解法应该substring也能套用吧?

看大家都在讨论第二题，可不可以说说第一题的思路？

请问楼主，我下面的这几个test case是对的吗？

1. 
   
2. // s1 = "BABA"
   
3. // s2 = "CAB"
   
4. // false, -1
   
5. 
   
6. // s1 = "ABABAB"
   
7. // s2 = "CAB"
   
8. // true, 3
   
9. 
   
10. // s1 = "BABABA"
    
11. // s2 = "BABA"
    
12. // true, 3
    
13. 
    
14. // s1 = "aaaaaa"
    
15. // s2 = "aaaa"
    
16. // true, 2
    
17. 
    
18. 
    

复制代码

一点想法，如果修改后的s2 (记作ms2)要能重构成s1，那么ms2一定要是s1的前缀。从所有可能构成s1前缀的ms2出发，由长到短，且ms2需要满足：s1长度是这些前缀长度的整倍数k倍。匹配ms2 k倍，如果存在，倍数k即为答案，如果不行，试长度-1的另一个ms2，如果长度为1都不行，那就是不存在。

举个例子：

1. 
   
2. // s1 = "BABBABBABBAB" (len1 = 12)
   
3. // s2 = "CCBABB" (len2 = 6)
   
4. // true, 4
   
5. 
   
6. // start from length 6, prefix of s1 is "BABBAB", we can't find it in s2, skip
   
7. // start from length 5, 12 is not k times of 5, skip
   
8. // start from length 4, prefix of s1 is "BABB", which is a subsequence of s2
   
9. //  then we compare, BABB | ABBA | BBAB ， 2nd length 4 substring not match, skip
   
10. // start from length 3, prefix of s1 is "BAB", which is a subsequence of s2
    
11. //  then we compare, BAB | BAB | BAB | BAB ，all length 3 substring match, return value 12 / 3 = 4
    
12. 
    
13. // if we get to length 1 prefix of s1, still does't match, we know there is not solution
    
14. 
    
15. // time complexity, at worse check  O(len2) times, each comparison, will take O(len1), so it should be O(len1 * len2)
    
16. 
    

复制代码