Chương trình tìm các chỉ mục trong đó các chuỗi con của một chuỗi khớp hoàn toàn với một chuỗi khác hoặc khác nhau hoàn toàn tại một vị trí trong python

Giả sử, chúng ta được cung cấp hai chuỗi. Chuỗi đầu tiên có độ dài lớn hơn chuỗi thứ hai và chúng ta phải kiểm tra xem các chuỗi con từ chuỗi đầu tiên có khớp chính xác với chuỗi thứ hai hay khác nhau ở một vị trí. Chúng tôi trả về các chỉ mục của chuỗi đầu tiên, nơi các chuỗi con có thể khớp với chuỗi thứ hai bắt đầu.

Vì vậy, nếu đầu vào là string1 ='tpoint', string2 ='pi', thì đầu ra sẽ là 1 2.

Chuỗi con từ chuỗi đầu tiên khớp với chuỗi thứ hai hoặc khác ở một vị trí tại chỉ mục 1 và 2 là 'po' và 'oi'.

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

• Xác định một hàm tìm kiếm (). Điều này sẽ nhận string1, string2
  • str_cat:=string1 + string2
  • z_list:=một danh sách mới có kích thước của str_cat được khởi tạo bằng 0
  • z_list [0]:=kích thước của str_cat
  • đúng:=0
  • trái:=0
  • đối với tôi trong phạm vi từ 1 đến kích thước của str_cat, thực hiện
    • nếu tôi> đúng, thì
      • j:=0
      • while j + i
      • j:=j + 1
    • z_list [i]:=j
    • nếu j> 0, thì
      • left:=i
      • đúng:=i + j - 1
  • nếu không,
    • k:=i - left
    • r_len:=right - i + 1
    • nếu z_list [k]
    • z_list [i]:=z_list [k]
  • nếu không,
    • m:=right + 1
    • while m
    • m:=m + 1
    • z_list [i]:=m - i
    • left:=i
    • đúng:=m - 1

Ví dụ

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

def search(string1, string2):
   str_cat = string1 + string2
   z_list = [0] * len(str_cat)
   z_list[0] = len(str_cat)
   right = 0
   left = 0
   for i in range(1, len(str_cat)):
      if i > right:
         j = 0
         while j + i < len(str_cat) and str_cat[j] == str_cat[j+i]:
            j += 1
         z_list[i] = j
         if j > 0:
            left = i
            right = i + j - 1
      else:
         k = i - left
         r_len = right - i + 1
         if z_list[k] < r_len:
            z_list[i] = z_list[k]
         else:
            m = right + 1
            while m < len(str_cat) and str_cat[m] == str_cat[m -i]:
               m += 1
            z_list[i] = m - i
            left = i
            right = m - 1
      z_list[i] = min(len(string1), z_list[i])
   return z_list[len(string1):]

def solve(str1, str2):
   fwd = search(str2, str1)
   bwrd = search(str2[::-1], str1[::-1])
   bwrd.reverse()
   idx = []
   for i in range(len(str1) - len(str2)+1):
      if fwd[i] + bwrd[i+len(str2)-1] >= len(str2)-1:
         idx.append(str(i))
   if len(idx) == 0:
      return False
   else:
      return (" ".join(idx))

print(solve('tpoint', 'pi'))

Đầu vào

'tpoint', 'pi'

Đầu ra

1 2