Pythonのsの個別の部分文字列の数をカウントするプログラム

文字列sがあるとすると、sの個別の空でない部分文字列の数を見つける必要があります。

したがって、入力がs ="abaa"の場合、サブストリングは["a"、 "b"、 "ab"、 "ba"、 "aa"、 "aba"、 "であるため、出力は8になります。 baa "、"abaa"]。

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

• トライ：=新しい地図
• n：=sのサイズ
• 0からn-1の範囲のiの場合、do
  • curr：=trie
  • iからn-1の範囲のjの場合、do
    • c：=s [j]
    • cがcurrにない場合は、
      • curr [c]：=新しいマップ
    • curr：=curr [c]
    • curr ["*"]：=True
• q：=キューを作成し、トライを挿入します
• ans：=0
• qが空ではない場合は、
  • ans：=ans + 1
  • t：=qのアイテムを残し、このアイテムをqから削除します
  • tのcごとに、
    • cが"*"と同じでない場合、
      • qの最後にt[c]を挿入します
• return ans-1

例

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

from collections import deque
def solve(s):
   trie = {}
   n = len(s)
   for i in range(n):
      curr = trie
      for j in range(i, n):
         c = s[j]
         if c not in curr:
            curr[c] = {}
         curr = curr[c]
         curr["*"] = True

   q = deque([trie])
   ans = 0
   while q:
      ans += 1
      t = q.popleft()
      for c in t:
         if c != "*":
            q.append(t[c])
   return ans - 1

s = "abaa"
print(solve(s))

入力

"abaa"

出力

8