2

特定の文字列の主要な循環部分文字列を見つけるアルゴリズムを探しています。

巡回部分文字列:

  • 隣接して 2 回以上繰り返される部分文字列。

支配的な巡回部分文字列:

  • 最も隣接する繰り返しを持つ部分文字列が支配的です
  • (隣接する繰り返しは同じ回数発生します)
    • 最も長い部分文字列が支配的です
  • (長さのタイと隣接する繰り返し)
    • 最初に現れる部分文字列が支配的です

例 1:

  • prefixgarbagecyclecyclecyclecyclesufixgarbage
  • 戻り値cycle:=>cycleは、最も繰り返される隣接する部分文字列です

例 2:

  • prefixgarbagecyclepadinggarbagecyclesufixgarbage
  • を返しますg:=> の出現はcycle隣接して繰り返されず、隣接してg2 回繰り返されます

例 3:

  • prefixgarbagecyclecyclepadinggarbageprefixgarbage
  • cycle:=>を返しますcycle&g隣接して 2 回繰り返しますが、cycleそれよりも長くなりますg

例 4:

  • prefixgarbagecyclecyclecycleroundroundroundprefixgarbage
  • cycle:=>を返しますcycle&round隣接して 3 回繰り返します & 同じ長さですが、cycle最初に表示されます

例 5:

  • abcdefghijklmnopqrstuvqxyz
  • <empty string>繰り返される隣接する部分文字列がないため、戻ります

このアルゴリズムを実装するための最良のアプローチは何ですか?

4

4 に答える 4

2

この二次時間アルゴリズム (Python で実装) よりも優れたものは見つかりません。

IREP, IPER, IPOS = 0, 1, 2

def find_dominant(src):
  best = (0, 0, 0) # repetitions-1, period, position

  period = 0
  while period < len(src) // max(2, 1 + best[IREP]):
    period += 1
    length = 0

    for pos in range(len(src) - 1 - period, -1, -1):
      if src[pos] == src[pos + period]:
        length += 1
        repetitions = length // period
        if repetitions >= best[IREP]:
          best = (repetitions, period, pos)
      else:
        length = 0

  return best


s = "prefixgarbagecyclecyclecyclecyclesufixgarbage"
res = find_dominant(s)
if res[0] == 0:
  print("nothing found")
else:
  print(res[IREP] + 1, '*', s[res[IPOS]: res[IPOS] + res[IPER]])

可能な期間ごとに文字列をスキャンし、最も長い周期的なサブシーケンスを覚えておいてください。後方にスキャンして、より少ない条件を確認します。それ以上の改善が見られない場合は、期間の増加を停止します。

時間計算量は O(N 2 / R) です。ここで、R は主要部分文字列の繰り返し回数です。スペースの複雑さは O(1) です。

于 2013-09-13T19:18:03.530 に答える
1

これが可能なアプローチです（サイクルが隣接している必要があるという事実により、より簡単になります）。文字列を選択します。繰り返されるかどうかを確認します。最も繰り返されるものを追跡します。

実際にテストされた Python コードを編集します。

testStrings =[ "prefixgarbagecyclecyclecyclecyclesufixgarbage",
               "prefixgarbagecyclepadinggarbagecyclesufixgarbage",
               "prefixgarbagecyclecyclepadinggarbageprefixgarbage",
               "prefixgarbagecyclecyclecycleroundroundroundprefixgarbage",
               "abcdefghijklmnopqrstuvqxyz"];

for input in testStrings:

 repCountMax = 0
 longestCycle = ""
 repCount = 0
 for i in range (1, len(input)):
  for j in range( i+1, len(input)):
    substring = input[i:j]
    #print substring
    ls = len(substring)
    repCount = 1
    k = j
    while(substring == input[k:k+ls]):
      k = k + ls
      repCount = repCount +1
      #print "repetition ", repCount, " of ", substring, "\n"
    if (repCount > repCountMax) or ((repCount == repCountMax) and len(substring) > len(bestCycle)):
      repCountMax = repCount
      bestCycle = substring

 if repCountMax > 1:
  print "best cycle in '", input, "' is '", bestCycle,"' which is repeated ", repCountMax, " times."
 else:
  print "no repeated cycles found in string ", input

結果の出力:

'prefixgarbagecyclecyclecyclecyclesufixgarbage' の最適なサイクルは、4 回繰り返される 'ecycl' です。

'prefixgarbagecyclepadinggarbagecyclesufixgarbage' の最適なサイクルは 'g' で、2 回繰り返されます。

'prefixgarbagecyclecyclepadinggarbageprefixgarbage' の最適なサイクルは、2 回繰り返される 'ecycl' です。

'prefixgarbagecyclecyclecycleroundroundroundprefixgarbage' の最適なサイクルは、3 回繰り返される 'ecycl' です。

文字列 abcdefghijklmnopqrstuvqxyz に繰り返されるサイクルが見つかりません

注 - 見つかったサイクルはecyclではなく でしcycleた。ecycl最初に発生した...

2 番目の注意 - 現在の最良の見積もりを「打ち負かす」ことができなくなったときに停止することで、物事をわずかに効率的にすることができます。 6回の繰り返しのためのtスペース。これにより、かなりの数の繰り返しがある場合に速度が向上します。それを実装する方法については、エフゲニーのソリューションを参照してください。

于 2013-09-13T18:46:16.080 に答える