Triển khai strStr() trong Python

Cho chuỗi str và sub_str. Tìm vị trí đầu tiên sub_str xuất hiện trong str. Ví dụ: "helloworld", "lo" → 3.

Giải pháp

Duyệt hai con trỏ:

• i=0, j=0, m=len(needle), n=len(haystack).
• Nếu m=0 → 0.
• Trong khi i=m: nếu khớp thì kiểm tra tiếp, nếu đủ m → trả vị trí; else i++.

Ví dụ

Triển khai Python:

class Solution(object): 
    def strStr(self, haystack, needle): 
        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