পাইথনে বিভিন্ন প্রশ্নের জন্য একটি স্ট্রিংয়ের বিভিন্ন সাবস্ট্রিংয়ের সংখ্যা খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি স্ট্রিং s আছে যার দৈর্ঘ্য n। আমাদের কাছে প্রশ্নগুলির একটি তালিকাও রয়েছে, যেখানে Q[i] একটি জোড়া (l, r) রয়েছে। প্রতিটি প্রশ্নের জন্য আমাদেরকে l এবং r-এর মধ্যে অন্তর্ভুক্ত পরিসরে s-এর বিভিন্ন সাবস্ট্রিং-এর সংখ্যা গণনা করতে হবে।

সুতরাং, যদি ইনপুটটি s ="ppqpp" Q =[(1,1),(1,4),(1,1),(0,2)] এর মত হয়, তাহলে আউটপুট হবে [1,8, 1,5] কারণ

• প্রশ্নের জন্য (1, 1) একমাত্র সাবস্ট্রিং হল 'p' তাই আউটপুট হল 1

• প্রশ্নের জন্য (1, 4) সাবস্ট্রিংগুলি হল 'p', 'q', 'pq', 'qp', 'pp', 'pqp', 'qpp' এবং 'pqpp', তাই আউটপুট হল 8

• আবার কোয়েরির জন্য (1, 1) একমাত্র সাবস্ট্রিং হল 'p' তাই আউটপুট হল 1

• কোয়েরির জন্য (0, 2) সাবস্ট্রিংগুলি হল 'p', 'q', 'pp', 'pq', 'ppq', তাই আউটপুট হল 8৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন সংজ্ঞায়িত করুন kasai()। এটি s, suff, n
লাগবে
• lcp :=n আকারের একটি অ্যারে এবং 0 দিয়ে পূরণ করুন
• inv :=n আকারের একটি অ্যারে এবং 0 দিয়ে পূরণ করুন
• আমি 0 থেকে n - 1 রেঞ্জের জন্য, কর
  • inv[suff [i]] :=i
• k :=0
• আমি 0 থেকে n - 1 রেঞ্জের জন্য, কর
  • যদি inv [i] n-1 এর মত হয়, তাহলে
    • k :=0
    • পরবর্তী পুনরাবৃত্তির জন্য যান
  • j :=suff[inv [i] + 1]
  • যদিও i + k
  • k :=k + 1
• lcp[inv [i]] :=k
• যদি k> 0, তারপর
  • k :=k - 1

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

def kasai (s, suff, n):
   lcp = [0] * n
   inv = [0] * n
   for i in range (n):
      inv [suff [i]] = i
   k = 0
   for i in range (n):
      if inv [i] == n-1:
         k = 0
         continue
      j = suff [inv [i] + 1]
      while i + k <n and j + k <n and s [i + k] == s [j + k]:
         k += 1
      lcp [inv [i]] = k
      if k> 0:
         k -= 1
   return lcp

def solve(s, Q):
   res = []
   for i in range (len(Q)):
      left, right = Q[i]
      sub = s [left: right + 1]
      length = right-left + 1

      suffix = [[i, sub [i:]] for i in range (length)]

      suffix.sort (key = lambda x: x [1])
      suff, suffix = [list (t) for t in zip (* suffix)]

      lcp = kasai (sub, suff, length)
      count = len (suffix [0])
      for i in range (length-1):
         count += len (suffix [i + 1]) - lcp [i]

      res.append(count)
   return res

s = "pptpp"
Q = [(1,1),(1,4),(1,1),(0,2)]
print(solve(s, Q))

ইনপুট

"pptpp", [(1,1),(1,4),(1,1),(0,2)]

আউটপুট

[1, 8, 1, 5]