Pythonの文字列にアナグラムが存在するすべてのサブ文字列を検索するプログラム

小文字の文字列sがあるとします。 s内の別の場所に別の部分文字列が存在する必要があるすべての部分を検索する必要があります。これは、取得した部分文字列のアナグラムです。辞書式順序で部分文字列のリストを見つける必要があります。

したがって、入力がs ="abcba"のような場合、出力は['a'、'a'、'ab'、'abc'、'abcb'、'b'、'b'、'ba'になります。 、'bc'、'bcba'、'cb'、'cba']それぞれについて、文字列自体に存在するさまざまなアナグラムを見つけることができます。

これを解決するには、次の手順に従います-

• res：=新しいリスト

• L：=sのサイズ

• 1からLの範囲のiの場合、実行します

  • smap：=空の辞書であり、すべての値はリスト型です

  • 0からL-iの範囲のjの場合、実行

    • cs：=インデックスjからj+i-1までのsの部分文字列]

    • k：=csのアイテムをソートされた形式で結合した後の文字列

    • smap [k]

      の最後にcsを挿入します

  • smapの各キーkと値vについて、実行します

    • サイズがv>=2の場合、

      • vの要素をresに挿入します

• 並べ替え後に解像度を返す

例

理解を深めるために、次の実装を見てみましょう

from collections import defaultdict
def solve(s):
   res = []
   L = len(s)
   for i in range(1, L + 1):
      smap = defaultdict(list)
      for j in range(L - i + 1):
         cs = s[j : j + i]
         k = "".join(sorted(cs))
         smap[k].append(cs)
      for k, v in smap.items():
         if len(v) >= 2:
            res.extend(v)

   return sorted(res)

s = "abcba"
print(solve(s))

入力

"abcba"

出力

['a', 'a', 'ab', 'abc', 'abcb', 'b', 'b', 'ba', 'bc', 'bcba', 'cb', 'cba']