两个大字符串中的部分字符串匹配(Partial String matching in two large strings)

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

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

这应该返回“他的”，“hisismyfir”，“字符串”等。

这可能吗？

问候..

I am looking for an efficient algorithm to find out all partial matches in 2 large strings. For example,

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

This should return "his", "hisismyfir", "string", etc.

Is this possible?

Regards..

最满意答案

构造一个布尔矩阵M，其中M（i，j）告诉你一个字符串的第i个字符是否与另一个字符串的第j个字符匹配。 匹配的子串现在将是M中的对角线，所以现在走遍矩阵并寻找那些。

Construct a boolean matrix M where M(i,j) tells you if the i'th character of one string matches the j'th character of the other. A matching substring will now be a diagonal line of true in M, so now walk the matrix and look for those.

更多推荐