0

以下のように組み立てられた問題のパズルの場合

2 つの文字列 A と B について、文字列の類似性を、両方の文字列に共通する最長のプレフィックスの長さと定義します。たとえば、文字列 "abc" と "abd" の類似度は 2 ですが、文字列 "aaa" と "aaab" の類似度は 3 です。文字列 S とその接尾辞のそれぞれの類似度の合計を計算します。

次のソリューションを作成しましたが、3 つのテスト ケースしかパスできませんが、失敗するテスト ケースを特定できません。失敗するシナリオを特定するのを手伝ってくれませんか。

入力例: 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 番目のケースの場合、答えは 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 に答える