Triển khai strStr () bằng Python

Giả sử chúng ta có hai chuỗi str và sub_str. Chúng ta phải tìm lần xuất hiện đầu tiên của sub_str trong str. Vì vậy, nếu chuỗi str là "helloworld" và chuỗi con là "lo", thì kết quả sẽ là 3.

Điều này có thể được thực hiện bằng cách sử dụng hàm strstr () trong C. Chúng ta phải thiết kế một hàm khác tương tự như hàm strstr () trong C.

Để giải quyết vấn đề này, hãy làm theo các bước sau -

• i:=0, j:=0, m:=length of sub_str và n:=length of str
• nếu m =0, thì trả về 0
• while i
• nếu str [i] =sub_str [j], thì
  • tạm thời:=j
  • while j
  • tăng i và j lên 1
• nếu j =m, thì trả về nhiệt độ
• i:=temp + 1
• j:=0

Hãy cho chúng tôi xem việc triển khai để hiểu rõ hơn

Ví dụ (Python)

class Solution(object):
   def strStr(self, haystack, needle):
      """
      :type haystack: str
      :type needle: str
      :rtype: int
      """
      i = 0
      j = 0
      m = len(needle)
      n = len(haystack)
      if m ==0:
         return 0
      while i<n and n-i+1>=m:
         if haystack[i] == needle[j]:
            temp = i
            while j<m and i<n and needle[j]==haystack[i]:
               i+=1
               j+=1
            if j == m:
               return temp
            i= temp+1
            j = 0
         else:
            i+=1
      return -1
haystack = "helloworld"
needle = "lo"
ob1 = Solution()
print(ob1.strStr(haystack, needle))

Đầu vào

haystack = "helloworld"
needle = "lo"

Đầu ra

3