Viết chương trình Python để đếm số lần xuất hiện của một chuỗi con trong một chuỗi

Đếm () là một hàm tích hợp trong Python. Nó sẽ trả về tổng số của một phần tử đã cho trong một chuỗi. Việc đếm bắt đầu từ đầu chuỗi cho đến khi kết thúc. Cũng có thể chỉ định chỉ mục bắt đầu và kết thúc từ nơi bạn muốn bắt đầu tìm kiếm

Trong hướng dẫn Python này, bạn sẽ học

Cú pháp cho PythonString Count()

Cú pháp hàm đếm trong Python

string.count(char or substring, start, end)

Các tham số của Cú pháp Python

• Char hoặc chuỗi con. Bạn có thể chỉ định một ký tự hoặc chuỗi con mà bạn muốn tìm kiếm trong chuỗi đã cho. Nó sẽ trả về cho bạn số ký tự hoặc chuỗi con trong chuỗi đã cho
• bắt đầu. (tùy chọn) Nó cho biết chỉ mục bắt đầu từ nơi tìm kiếm sẽ bắt đầu. Nếu không được cung cấp, nó sẽ bắt đầu từ 0. Ví dụ: bạn muốn tìm kiếm một ký tự từ giữa chuỗi. Bạn có thể cung cấp giá trị bắt đầu cho hàm đếm của mình
• kết thúc. (tùy chọn) Nó cho biết chỉ mục kết thúc nơi tìm kiếm kết thúc. Nếu không được cung cấp, nó sẽ tìm kiếm cho đến khi kết thúc danh sách hoặc chuỗi đã cho. Ví dụ: bạn không muốn quét toàn bộ chuỗi và giới hạn tìm kiếm cho đến một điểm cụ thể, bạn có thể đặt giá trị kết thúc trong hàm đếm của mình và bộ đếm sẽ đảm nhiệm việc tìm kiếm cho đến thời điểm đó

Giá trị trả về

Phương thức count() sẽ trả về một giá trị số nguyên, i. e. , số phần tử đã cho từ chuỗi đã cho. Nó trả về 0 nếu không tìm thấy giá trị trong chuỗi đã cho

ví dụ 1. Phương pháp đếm trên một chuỗi

Ví dụ sau đây cho thấy sự xuất hiện của một ký tự trong một chuỗi nhất định cũng như trong bằng cách sử dụng chỉ mục bắt đầu/kết thúc

Trong bài viết này, chúng ta sẽ tìm hiểu cách đếm số lần xuất hiện của chuỗi con trong chuỗi trong Python. Chúng ta sẽ thảo luận về các mã có chức năng tích hợp, không có chức năng tích hợp. Trước tiên chúng ta hãy xem nhanh chuỗi trong Python là gì

Chuỗi Python

Chuỗi là một loại trong ngôn ngữ python giống như số nguyên, số float, boolean, v.v. Dữ liệu được bao quanh bởi dấu nháy đơn hoặc nháy kép được gọi là một chuỗi. Chuỗi còn được gọi là dãy ký tự

string1 = "apple"
string2 = "Preeti125"
string3 = "12345"
string4 = "pre@12"

Trong Python, chúng ta có thể đếm số lần xuất hiện của một chuỗi con từ một chuỗi đã cho bằng ba phương thức khác nhau. Các mã được đề cập sẽ trả về số lần một chuỗi con xuất hiện trong một chuỗi

Ví dụ,

Ví dụ. Đếm số lần xuất hiện của chuỗi con bằng thuật toán tìm kiếm mẫu

Đây là một giải pháp đơn giản để khớp từng ký tự của một chuỗi con và chúng tôi tăng bộ đếm lên 1 khi chúng tôi nhận được kết quả khớp hoàn chỉnh cho chuỗi con. Chương trình này thường hữu ích cho những người đang tìm kiếm một thuật toán mà không cần sử dụng bất kỳ chức năng tích hợp nào

Thời gian phức tạp. Ô(M*N)

def count(sub, s): 
    M = len(sub) 
    N = len(s) 
    res = 0

    # A loop to slide sub[] one by one
    for i in range(N - M + 1): 

        # For current index i, check for the match
        j = 0
        while(j < M): 
            if (s[i + j] != sub[j]): 
                break
            j += 1

        if (j == M): 
            res += 1
            j = 0
    return res 

# Driver Code 
string = "abracadabra"
substring = "bra"
print("Count:", count(substring, string))

Đếm. 2

Ví dụ. Đếm số lần xuất hiện của chuỗi con bằng thuật toán KMP

Giải pháp này dựa trên thuật toán KMP(Knuth Morris Pratt). Ý tưởng cơ bản đằng sau thuật toán này là nó phát hiện mẫu hoặc chuỗi con không khớp thay vì mẫu phù hợp. mảng lps[] được sử dụng để bỏ qua các ký tự trong khi khớp. Sau đây là một mã tự giải thích. Chúng ta sẽ xem xét chi tiết thuật toán này trong một bài viết khác

Thời gian phức tạp. Ô(M+N)

def count(sub, s): 

    M = len(sub) 
    N = len(s) 

    # Create lps[] that will hold the longest prefix suffix values for subtern 
    lps = [None] * M 
    j = 0 # index for sub[] 

    # Preprocess the substring (calculate lps[] array) 
    lps_Array(sub, M, lps) 

    i = 0 # index for s[] 
    res = 0
    next_i = 0

    while (i < N): 
        if sub[j] == s[i]: 
            j = j + 1
            i = i + 1
        if j == M: 

            # When we find substring first time, we iterate again to check if there exists more substring
            j = lps[j - 1] 
            res = res + 1

            # We start i to check for more than once appearance of substring, we will reset i to previous start+1 
            if lps[j] != 0: 
                next_i = next_i + 1
                i = next_i 
                j = 0

        # Mismatch after j matches 
        elif ((i < N) and (sub[j] != s[i])): 
    
        # Do not match lps[0..lps[j-1]] characters, they will match anyway 
            if (j != 0): 
                j = lps[j - 1] 
            else: 
                i = i + 1

    return res 

def lps_Array(sub, M, lps): 

    # Length of the previous longest prefix suffix 
    len = 0
    i = 1
    lps[0] = 0 # lps[0] is always 0 

    # The loop calculates lps[i] for i = 1 to M-1 
    while (i < M): 
        if sub[i] == sub[len]: 
            len = len + 1
            lps[i] = len
            i = i + 1

        else: # (sub[i] != sub[len]) 

            # search the step 
            if len != 0: 
                len = lps[len - 1] 

            else: # if (len == 0) 
                lps[i] = len
                i = i + 1

# Driver code 
string = "abracadabra"
substring = "bra"
print("Count:", count(substring, string))

Đếm. 2

Ví dụ. Đếm số lần xuất hiện của chuỗi con bằng hàm đếm ()

Trong ví dụ này, chúng tôi sử dụng hàm count() tích hợp để đếm số lần xuất hiện của chuỗi con trong chuỗi đã cho. Nó lấy chuỗi con làm đối số. Ngoài ra, bạn có thể cung cấp các đối số chuỗi con, bắt đầu và dừng để tìm một chuỗi con trong một phạm vi

Thời gian phức tạp. TRÊN)

string = "abracadabra"
substring = "bra"
ct = string.count(substring)
print("Count:",ct)

Đếm. 2

Phần kết luận

Trong bài viết này, chúng ta đã học cách đếm số lần xuất hiện của một chuỗi con trong một chuỗi đã cho trong Python bằng cách sử dụng một số phương thức. Chúng tôi đã sử dụng một số thuật toán đơn giản như tìm kiếm mẫu mà không cần bất kỳ hàm tích hợp nào, thuật toán KMP và hàm đếm () để đếm số lần xuất hiện. Chúng tôi đã thảo luận rằng tất cả các phương pháp này cùng với sự phức tạp về thời gian của chúng

Làm cách nào để tìm các lần xuất hiện của chuỗi con trong chuỗi bằng Python?

Làm cách nào để tìm số lần một chuỗi con xuất hiện trong một chuỗi trong Python?