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

Question

假设我有两个字符串：

"hello"
"love"

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

这是另一个例子：

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

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

我的想法如下：

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

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

谢谢！

编辑 我也需要字符串。

Answer 1

这是一个众所周知的问题，称为最长公共子串。可以使用动态编程方法在O(mn)、 wherem和nare 中求解单个字符串的长度。维基百科中的文章包含易于理解的伪代码。