Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình tìm số cặp chuỗi con bằng nhau trong Python

Giả sử chúng ta được cung cấp hai chuỗi, cả hai đều được làm bằng bảng chữ cái viết thường. Chúng ta phải tìm ra số phần tư (p, q, r, s) thỏa mãn các điều kiện cho trước -

  • 0 <=p <=q <=độ dài của chuỗi đầu tiên.

  • 0 <=r <=s <=độ dài của chuỗi thứ hai.

  • Chuỗi con bắt đầu từ chỉ mục p của chuỗi đầu tiên và kết thúc ở chỉ mục q của chuỗi đầu tiên, phải bằng chuỗi con bắt đầu từ chỉ mục q của chuỗi thứ hai và kết thúc ở chỉ mục r của chuỗi thứ hai.

  • q - r phải là giá trị nhỏ nhất có thể có trong tất cả các phần tư thỏa mãn điều kiện trên.

Chúng ta phải tìm ra số phần tư như vậy.

Vì vậy, nếu đầu vào giống như firstString ='hgfn', secondString ='gfrt', thì đầu ra sẽ là 2.

Có hai phần tư (1, 1, 0, 0) và (2, 2, 1, 1) thỏa mãn các điều kiện và có giá trị nhỏ nhất đối với q - r.

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

  • Định nghĩa một hàm ord (). Điều này sẽ mất ch
    • trả về giá trị unicode của ch
  • Từ phương thức chính, hãy làm như sau -
  • left:=một danh sách mới có kích thước 26 chứa giá trị vô cực
  • right:=một danh sách mới có kích thước 26 chứa giá trị -1
  • res:=0
  • mi:=infinity
  • đối với mỗi chỉ mục i và ký tự ch trong Chuỗi đầu tiên, thực hiện
    • left [ord (ch) - ord ('a')]:=tối thiểu của (left [ord (ch) - ord ('a')], i)
  • đối với mỗi chỉ mục i và ký tự ch trong chuỗi thứ hai, thực hiện
    • right [ord (ch) - ord ('a')]:=tối đa bên phải [ord (ch) - ord ('a')], i
  • đối với tôi trong phạm vi từ 0 đến 25, hãy thực hiện
    • nếu left [i] không giống -1, thì
      • mi:=tối thiểu trong tổng số (mi, left [i] - right [i])
  • đối với tôi trong phạm vi từ 0 đến 25, hãy thực hiện
    • nếu trái [i] không giống với vô cùng và phải [i] không giống -1, thì
      • nếu left [i] - right [i] giống với mi, thì
        • res:=res + 1
  • trả lại res

Ví dụ

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

def solve(firstString, secondString):
   left = [float('inf')] * 26
   right = [-1] * 26
   res = 0
   mi = float('inf')
   for i, ch in enumerate(firstString):
      left[ord(ch) - ord('a')] = min(left[ord(ch) - ord('a')], i)
   for i, ch in enumerate(secondString):
      right[ord(ch) - ord('a')] = max(right[ord(ch) - ord('a')], i)
   for i in range(26):
      if left[i] != -1:
         mi = min(mi, left[i] - right[i])
   for i in range(26):
      if left[i] != float('inf') and right[i] != -1:
         if left[i] - right[i] == mi:
            res += 1
   return res

print(solve('hgfn', 'gfrt'))

Đầu vào 

'hgfn', 'gfrt'

Đầu ra 

2