string - 找到同时也是后缀的前缀

Question

我正在寻找这个问题的最佳解决方案。

给定一个长度为 n 的字符串 s，找到一个从左到右的前缀等同于一个从右到左的后缀。

前缀和后缀可以重叠。

示例:给定abababa，前缀是[ababa]ba，后缀是ab[ababa]。

我能做到这一点

1. 对于每个 i = 0 到 n-1，取以 i 结尾的前缀，看看我们是否有合适的后缀。它的时间是 O(n^2) 时间和 O(1) 空间。

2. 我想出了一个优化方法，我们对所有字符的位置进行索引。这样，我们就可以从 1/中消去样本空间集。同样，最坏情况下的复杂度是 O(n^2) 和 O(n) 额外空间。

有没有更好的算法？

Answer 1

利用 KMP 算法。算法的状态决定了“大海捞针的最长后缀仍然是针的前缀”。因此，只需将您的字符串作为针，将没有第一个字符的字符串作为大海捞针。在 O(N) 时间和 O(N) 空间内运行。

带有一些示例的实现:

public static int[] create(String needle) {
    int[] backFunc = new int[needle.length() + 1];
    backFunc[0] = backFunc[1] = 0;
    for (int i = 1; i < needle.length(); ++i) {
        int testing = i - 1;
        while (backFunc[testing] != testing) {
            if (needle.charAt(backFunc[testing]) == needle.charAt(i-1)) {
                backFunc[i] = backFunc[testing] + 1;
                break;
            } else {
                testing = backFunc[testing];
            }
        }
    }
    return backFunc;
}

public static int find(String needle, String haystack) {
    // some unused character to ensure that we always return back and never reach the end of the
    // needle
    needle = needle + "$";
    int[] backFunc = create(needle);
    System.out.println(Arrays.toString(backFunc));
    int curpos = 0;
    for (int i = 0; i < haystack.length(); ++i) {
        while (curpos != backFunc[curpos]) {
            if (haystack.charAt(i) == needle.charAt(curpos)) {
                ++curpos;
                break;
            } else {
                curpos = backFunc[curpos];
            }
        }
        if (curpos == 0 && needle.charAt(0) == haystack.charAt(i)) {
            ++curpos;
        }
        System.out.println(curpos);
    }
    return curpos;
}

public static void main(String[] args) {
    String[] tests = {"abababa", "tsttst", "acblahac", "aaaaa"};
    for (String test : tests) {
        System.out.println("Length is : " + find(test, test.substring(1)));
    }
}