java - 查找长度在 x 和 y 之间的最长重复子串

Question

给定一个字符串:“blablafblafbla”和 2 个限制:x=3，y=5 我想找到长度在 x 和 y 之间的最长重复子串。如果有很多，第一个 在我的例子中是“blaf” 几个问题: 1.使用正则表达式更容易吗？ 2.我知道如何找到最长的子串，但我必须在哪里设置条件才能使它位于 x 和 y 之间？

public static String longestDuplicate(String text)
{
    String longest = "";
    for (int i = 0; i < text.length() - 2 * longest.length() * 2; i++)
    {
        OUTER: for (int j = longest.length() + 1; j * 2 < text.length() - i; j++)
        {
            String find = text.substring(i, i + j);
            for (int k = i + j; k <= text.length() - j; k++)
            {
                if (text.substring(k, k + j).equals(find))
                {
                    longest = find;
                    continue OUTER;
                }
            }
            break;
        }
    }
    return longest;
}

Answer 1

您提供的代码是解决您遇到的问题的一种极其低效的方法。我将使用 Rabin-Karp 实现解决方案或其他一些滚动哈希算法，这将使您能够解决复杂度为 O((y-x) * L) 的问题。

您不能在此处使用正则表达式 - 它们旨在解决完全不同的任务。

关于如何使用您的解决方案 找到长度在x 和y 之间的最长子串的问题，只需修改循环j 仅考虑区间 [x, y] 中的值。以下是您可以如何做到这一点。

for (int j = Math.max(longest.length() + 1, x) ; j * 2 < text.length() - i && j < y; j++)

编辑:要找到最长的子串，反转 for 循环:

for (int j = Math.min((text.length() - i -1)/2, y) ; j > longest.length() && j >=x; j--)