两个大字符串中的部分字符串匹配

我正在寻找一种高效的算法来查找2个大字符串中的所有部分匹配。例如，两个大字符串中的部分字符串匹配

string 1: "Thisismyfirststring" 
string 2: "searchismyfirtestring"

这应返回 “他”， “hisismyfir”， “串” 等

这可能吗？

问候..

来源

2015-08-23 G Narayan

花点时间，格式化您的问题并使其可读。目前我无法得到你想要的东西。另外请确保您附上您认为有效/无效的相关代码。 – SMA

构建一个布尔矩阵M，其中M（I，J）告诉你，如果一个字符串的第i个字符其他的第j个字符匹配。一个匹配的子字符串现在是M中的对角线true，所以现在走矩阵并寻找那些。

来源

2015-08-23 06:14:55 Joni

谢谢乔尼。你能详细说一下吗？否则，我们是否有任何有效的内置包，因为我正在查看至少3000个字符的字符串，并且匹配可能会发生约300-400个字符。 –

我所描述的基本上是[最长公共子串]（https://en.wikipedia.org/wiki/Longest_common_substring_problem）的动态编程算法，您可以轻松地适应您的目的。 3000×3000字符的字符串导致只有10MB的布尔矩阵，所以这不是一个大问题。如果这是用于蛋白质或DNA测序，是的，有效的包装。 – Joni

两个大字符串中的部分字符串匹配

回答

相关问题