狗狗挂筋～

Ramily

idatascience 发表于 2018-6-16 03:32
**** 本内容被作者隐藏 ****

对哒对哒

chillin1017

感谢分享！努力攒上200！楼主加油！

hh821758

tinylic 发表于 2018-6-16 02:52
找到最小的i使得T【I..N】为原串S的subsequence，也就是找到T的最长后缀T'使得T'为S的subsequence，那么 ...

ok, 懂了，应该成立，给力给力！

idatascience

tinylic 发表于 2018-6-16 03:20
找的是目标传的最长后缀，这里就是S。最长后缀是14，因为314已经不是T的subsequence了。所以操作数是5-2= ...

嗯，跟rfamily说的做法本质是一样的。这个复杂度是n平方吧？

wenyitiger

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

tinylic

idatascience 发表于 2018-6-16 04:26
嗯，跟rfamily说的做法本质是一样的。这个复杂度是n平方吧？

可以用蠡口伞久尔的类似做法，是O(N)的

idatascience

tinylic 发表于 2018-6-16 06:14
可以用蠡口伞久尔的类似做法，是O(N)的

I see. 外循环target string，内循环放source string，然后match上几个就是几个。多谢大牛！！！

Self_Learner

感谢楼主的分享，祝楼主早日拿到心仪的offer～

Ramily

tinylic 发表于 2018-6-16 06:14
可以用蠡口伞久尔的类似做法，是O(N)的

还是没懂o(n)诶？判断是不是subsequence o(n)
但是不是要判断n次吗？
求指教！

Ramily

tinylic 发表于 2018-6-16 03:20
找的是目标传的最长后缀，这里就是S。最长后缀是14，因为314已经不是T的subsequence了。所以操作数是5-2= ...

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式