java - 有效地在两倍大的字符串中查找字符串

Question

我想看看一个数组中每个相邻数字之间的差异是否与另一个数组相同，或者它的旋转，例如

A = {1,2,4}, so the differences are {1,1,2}
B = {4,6,7}, the differences are {1,2,1}

如果将 {1,2,1} 中的所有元素顺时针移动一个元素，则结果为 {1,1,2}，这是正确的。

到目前为止，我将差异转换为字符串，然后查看第二个数组的差异是否在第一个与其自身连接的数组中找到

valid if "1 2 1" is in "1 1 2 1 1 2"

到目前为止我的代码看起来像这样 count是数组的长度，两者长度相同

    int c = count - 1;
    StringBuilder b1 = new StringBuilder();
    StringBuilder b2 = new StringBuilder();
    for (int i = 0; i < c; i++) {
        b1.append(array1[i + 1] - array1[i]);
        b1.append(" ");
        b2.append(array2[i + 1] - array2[i]);
        b2.append(" ");
    }
    b1.append((array1[0] - array1[c]) + d);
    b1.append(" ");
    b2.append((array2[0] - array2[c]) + d);

    String a2 = b2.toString();
    String a3 = b1.toString() + b1.toString();

    System.out.println(a3.contains(a2) ? "valid" : "not valid"); //bottleneck here

我的问题是，当我使用大数组(最多大约 250,000 个元素)时，我在 .contains() 的最后一行遇到了巨大的瓶颈。我想知道是否有比我正在使用的方法更快的方法来检查它是否在方法内部，或者我是否可以在构建字符串时进行检查，或者是否有一种完全不同的方法来执行此操作？

Answer 1

您需要一种比 contains 方法中使用的算法更有效的算法(它实际上取决于具体的实现，但看起来它在您使用的 Java 版本中效率不高).
您可以使用 Knuth-Morris-Pratt 算法:http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm 。在最坏的情况下它具有线性时间和空间复杂度，因此即使对于非常大的数组也能快速工作。请注意，无需将数组转换为字符串，因为该算法也适用于数组。