c++ - 最大相等字符串子数组

Question

假设我有两个字符串:

"hello"
"love"

字符串中最大子数组的大小为2:“lo”。

这是另一个例子:

"ABBABBA"
"BBABCBA"
Maximum subarray: "BBAB"
Size: 4

基本上，我怎样才能以最有效的方式解决这个问题？

我的想法是:

• 生成一个字符串的所有子数组
• 为另一个字符串生成所有子数组；
• 比较所有子数组
• 结果是最大匹配子数组的大小

但我认为这是一些看起来很糟糕的蛮力。知道如何改进吗？

谢谢!

编辑我也需要字符串。

Answer 1

这是一个众所周知的问题 Longest Common Substring .它可以在 O(mn) 中解决，其中 m 和 n 是各个字符串的长度，使用动态规划 方法。维基百科中的文章包含易于理解的伪代码。