0

对于如下框架的问题拼图

对于两个字符串 A 和 B，我们将字符串的相似度定义为两个字符串共有的最长前缀的长度。例如，字符串“abc”和“abd”的相似度为2，而字符串“aaa”和“aaab”的相似度为3。计算字符串S与其每个后缀的相似度之和。

我编写了以下解决方案，它只能通过三个测试用例，但我无法弄清楚它失败的测试用例，你能帮我找出它失败的场景吗？

样本输入：2 ababaa aa

样本输出：11 3

解释：对于第一种情况，字符串的后缀是“ababaa”、“babaa”、“abaa”、“baa”、“aa”和“a”。这些字符串中的每一个与字符串“ababaa”的相似度分别为 6,0,3,0,1,1。因此答案是 6 + 0 + 3 + 0 + 1 + 1 = 11。

对于第二种情况，答案是 2 + 1 = 3。

 def find_suffix(string):
        if len(string) == 0:
            return 0
        tail = 0
        head = 1
        occurences = [1]
        while head < len(string):
            if string[head] == string[tail]:
                occured = occurences[tail] + 1
                tail = tail + 1
            else:
                if string[0] == string[head]:
                    occured = 2
                    tail = 1
                else:
                    occured = 1
                    tail = 0

            occurences.append(occured)
            head = head + 1
        return sum(occurences)
4

1 回答 1

0

我不知道蟒蛇。我用方案语言编写了这段代码。它适用于 DrRacket

(define inp-string (read))

(define inp-list (string->list inp-string))

(define (sim-len l1 l2)
  (cond ((or (null? l1) (null? l2)) 0)
        ((char=? (car l1) (car l2)) (+ 1 (sim-len (cdr l1) (cdr l2))))
        (else
          0)))

(define inp-strlen (string-length inp-string))

(define iter-cnt 0)
(define final-ans 0)

(define (sum-of-sim l)
 (define (iter count)
   (cond ((null? l) 0)
         ((= iter-cnt inp-strlen) 0)
         (else
         (set! final-ans (+ final-ans 
         (sim-len inp-list (string->list (substring inp-string iter-cnt inp-strlen)))))
           (set! iter-cnt (+ iter-cnt 1))
    (iter iter-cnt))))
(iter iter-cnt))

(sum-of-sim inp-list)

final-ans

我测试的案例如下：

输入：- "" final-ans =0，输入：- "r" final-ans =1，输入：- "rajesh" final-ans =6，输入：- "rajesh bhat" final-ans=11，输入： - "rajraj" final-ans =9，输入：- "aaaaaa" final-ans =21

其他情况是什么？希望这可以帮助。

于 2012-05-04T16:01:49.700 回答