Chương trình đếm số chuỗi con tương tự cho mỗi truy vấn bằng Python

Giả sử chúng ta có hai chuỗi s và một tập truy vấn Q. Trong đó Q [i] chứa cặp (l, r), với mỗi chuỗi con của s từ l đến r, chúng ta phải tìm số chuỗi con s từ x đến y mà chúng tương tự nhau. Hai chuỗi s và t tương tự nhau nếu chúng tuân theo các quy tắc sau -

• Chúng có cùng độ dài

• Đối với mỗi cặp chỉ số (i, j), nếu s [i] giống với s [j], thì nó phải thỏa mãn t [i] =t [j], và tương tự nếu s [i] không giống với s [j], thì t [i] và t [j] phải khác nhau.

Vì vậy, nếu đầu vào là s =​​"hjhhbcbk" Q =[(1,2), (2,4)], thì đầu ra sẽ là [6, 1] vì

• Đối với truy vấn đầu tiên, các chuỗi con tương tự là "hj", "jh", "hb", "bc", "cb" và "bk".
• Đối với truy vấn đầu tiên, chuỗi con tương tự là "jhh"

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• fp:=một danh sách mới
• Xác định một hàm calc_fingerprint (). Điều này sẽ mất s
• dict:=một từ điển mới và ban đầu chèn cặp khóa-giá trị (s [0], 0)
• fp:="0"
• j:=1
• đối với tôi trong phạm vi từ 1 đến kích thước của s-1, hãy thực hiện
  • nếu s [i] không có trong dict, thì
    • dict [s [i]]:=j
    • j =j + 1
  • fp:=fp + biểu diễn chuỗi của dict [s [i]]
• trả về dạng số nguyên của fp
• Từ phương pháp chính, hãy thực hiện như sau -
• nếu kích thước của s> 10, thì
  • đối với tôi trong phạm vi từ 0 đến kích thước s - 10, hãy thực hiện
    • x:=calc_fingerprint (s [từ chỉ mục i đến i + 9])
    • chèn x vào cuối fp
• ret:=một danh sách mới
• đối với tôi trong phạm vi từ 0 đến kích thước là Q - 1, hãy thực hiện
  • (a, b):=Q [i]
  • s1:=chuỗi con của s từ chỉ mục a-1 đến b-1
  • k:=0
  • đối với tôi trong phạm vi từ 0 đến kích thước là s - (b-a), thực hiện
    • nếu b-a> 9 và fp [a-1] không giống với fp [i], thì
      • chuyển sang lần lặp tiếp theo
    • dict:=một bản đồ trống mới
    • s2:=chuỗi con của s từ chỉ mục i đến i + (b-a)
    • đối với tôi trong phạm vi từ 0 đến b-a, thực hiện
      • nếu s2 [i] không có trong dict, thì
        • nếu s1 [i] nằm trong các giá trị của dict, thì
          • ra khỏi vòng lặp
        • dict [s2 [i]]:=s1 [i]
      • nếu dict [s2 [i]] không giống với s1 [i], thì
        • ra khỏi vòng lặp
    • nếu không,
      • k:=k + 1
  • chèn k vào cuối ret
• trả lời lại

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

fp = []

def calc_fingerprint(s):
   dict = {s[0]: 0}
   fp = "0"
   j = 1
   for i in range(1, len(s)):
      if s[i] not in dict:
         dict[s[i]], j = j, j+1
      fp += str(dict[s[i]])
   return int(fp)

def solve(s, Q):
   if len(s) > 10:
      for i in range(0, len(s)-10):
         fp.append(calc_fingerprint(s[i: i+10]))

   ret = []
   for i in range(len(Q)):
      a, b = Q[i]
      s1 = s[a-1:b]
      k = 0
      for i in range(len(s)-(b-a)):
         if b-a > 9 and fp[a-1] != fp[i]:
            continue
         dict = {}
         s2 = s[i:i+(b-a)+1]
         for i in range(b-a+1):
            if s2[i] not in dict:
               if s1[i] in dict.values(): break
               dict[s2[i]] = s1[i]
            if dict[s2[i]] != s1[i]: break
         else:
            k += 1
      ret.append(k)

   return ret

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

Đầu vào

"hjhhbcbk", [(1,2), (2,4)]

Đầu ra

[6, 1]