4

PS：这不是如何找到2个序列之间的重叠，并返回它的副本

[虽然我要求上述方法的解决方案是否可以应用于以下问题]

问：虽然我做对了，但它仍然不是一个可扩展的解决方案，而且肯定没有优化（得分低）。阅读以下问题描述，并提供更好的解决方案。

问题：

为简单起见，我们要求前缀和后缀不为空且比整个字符串 S 短。字符串的边界S是任何既是前缀又是后缀的字符串。例如，"cut"是一个字符串的边框"cutletcut"，而一个字符串"barbararhubarb"有两个边框："b"和"barb"。

class Solution { public int solution(String S); }

即，给定一个由字符S组成的字符串N，返回在给定字符串中至少出现三个不重叠的最长边框的长度。如果 中没有这样的边框S，则该函数应返回 0。

例如，

  • 如果S = "barbararhubarb"函数应该返回1，如上所述；
  • 如果S = "ababab"函数应该返回2, as"ab"和"abab"都是 的边界S，但只有"ab"三个不重叠的事件；
  • 如果S = "baaab"函数应该返回0，因为它唯一的边界"b"只出现两次。

假使，假设：

  • N是范围内的整数[0..1,000,000]；
  • 字符串S仅由小写字母 ( a−z) 组成。

复杂：

  • 预期的最坏情况时间复杂度为O(N);
  • 预期的最坏情况空间复杂度为O(N)（不计算输入参数所需的存储空间）。

def solution(S):
    S = S.lower()
    presuf = []
    f = l = str()
    rank = []
    wordlen = len(S)
    for i, j in enumerate(S):
        y = -i-1
        f += S[i]
        l = S[y] + l
        if f==l and f != S:
            #print f,l
            new=S[i+1:-i-1]
            mindex = new.find(f)
            if mindex != -1:
                mid = f #new[mindex]
                #print mid
            else:
                mid = None
            presuf.append((f,mid,l,(i,y)))
    #print presuf
    for i,j,k,o in presuf:
        if o[0]<wordlen+o[-1]: #non overlapping
            if i==j:
                rank.append(len(i))
            else:
                rank.append(0)
    if len(rank)==0:
        return 0
    else:
        return max(rank)

我的解决方案时间复杂度是：O(N 2) 或 O(N 4) 非常感谢帮助。

4

5 回答 5

1

我的解决方案是结合 Rabin-Karp 和 Knuth-Morris-Pratt 算法。 http://codility.com/cert/view/certB6J4FV-W89WX4ZABTDRVAG6/details

于 2013-08-02T03:00:02.023 回答
0

我有一个带有后缀数组的解决方案（实际上有用于在线性时间内构造 SA 和 LCP 的算法，或者比这更糟糕的东西，但肯定不是二次的）。

仍然不确定我是否可以不使用 RMQ（使用 SegmentTree 的 O(log n)），我无法通过自己的案例并且看起来很复杂，但是使用 RMQ 可以（更不用说使用 for 循环而不是 RMQ 的方法，即无论如何都会使它成为二次方）。

解决方案的执行速度非常快，并通过了我设法制作的各种特权，通过了我的 21 个测试用例，但在他们的一些案例中仍然失败。不确定这是否对您有所帮助或让您知道如何解决问题，但我相信像@Vicenco 在他的一些评论中所说的那样天真的解决方案不能让您比 Silver 更好。

编辑： 设法解决了所有问题，但仍然很慢。我不得不强制执行一些条件，但不得不增加复杂性，仍然不知道如何优化它。会及时向大家发布。祝你好运！

于 2013-07-14T16:01:08.400 回答
0

我有一个执行 O(N) 或 O(N**3) 的 (Java) 解决方案，总体结果为 90/100，但我无法弄清楚如何通过 2 个不同的测试用例进行处理：

几乎_all_same_letters aaaaa...aa??aaaa??....aaaaaaa 2.150 秒。TIMEOUT ERROR 运行时间：>2.15 秒，时间限制：1.20 秒。

same_letters_on_both_ends 2.120 秒。TIMEOUT ERROR 运行时间：>2.12 秒，时限：1.24 秒。

编辑：搞定了！ 现在我有一个在 O(N) 中执行的解决方案，并通过了所有检查以得到 100/100 结果:) 我不知道 Codility，但它是一个很好的工具！

于 2013-07-09T06:14:08.980 回答
0 
protected int calcBorder(String input) {
    if (null != input) {
        int mean = (input.length() / 3);
        while (mean >= 1) {
            if (input.substring(0, mean).equals(
                    input.substring(input.length() - mean))) {
                String reference = input.substring(0, mean);
                String temp = input
                        .substring(mean, (input.length() - mean));
                int startIndex = 0;
                int endIndex = mean;
                int count = 2;
                while (endIndex <= temp.length()) {
                    if (reference.equals(temp.substring(startIndex,
                            endIndex))) {
                        count++;
                        if (count >= 3) {
                            return reference.length();
                        }
                    }
                    startIndex++;
                    endIndex++;
                }
            }
            mean--;
        }
    }
    return 0;
}
于 2014-12-16T15:51:45.223 回答
0

Z 算法将是一个很好的解决方案。

于 2016-01-30T05:06:45.310 回答