假设我有两个字符串:
"hello"
"love"
字符串中最大子数组的大小为2:“lo”。
这是另一个例子:
"ABBABBA"
"BBABCBA"
Maximum subarray: "BBAB"
Size: 4
基本上，我怎样才能以最有效的方式解决这个问题？
我的想法是:
- 生成一个字符串的所有子数组
- 为另一个字符串生成所有子数组；
- 比较所有子数组
- 结果是最大匹配子数组的大小
但我认为这是一些看起来很糟糕的蛮力。知道如何改进吗？
谢谢!
编辑 我也需要字符串。
最佳答案
这是一个众所周知的问题 Longest Common Substring .它可以在 O(mn) 中解决，其中 m 和 n 是各个字符串的长度，使用动态规划 方法。维基百科中的文章包含易于理解的伪代码。
关于c++ - 最大相等字符串子数组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10232938/