Chương trình tìm số dãy con riêng biệt trong Python

Giả sử chúng ta có một chuỗi s, chúng ta phải đếm số lượng các dãy con riêng biệt của chuỗi s. Nếu câu trả lời quá lớn thì trả về kết quả modulo 10 ^ 9 + 7.

Vì vậy, nếu đầu vào là s =​​"bab", thì đầu ra sẽ là 6 vì có 6 chuỗi khác nhau, đây là "a", "b," ba "," ab "," bb "," abb " .

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

• dp:=một mảng có kích thước bằng s và được lấp đầy bằng 0

• m:=10 ^ 9 + 7

• đối với mỗi chỉ mục i và char mục trong s, thực hiện

  • ind:=chỉ mục của ký tự thứ i trong s từ bên phải

  • dp [i]:=1 + (tổng của tất cả các phần tử trong dp [từ chỉ số 0 đến i-1]) mod m nếu ind giống -1 nếu ngược lại (tổng của tất cả các phần tử trong dp [từ chỉ mục ind đến i-1 ]) mod m

• trả về tổng của tất cả các phần tử trong dp mod m

Ví dụ

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

def solve(s):
   dp, m = [0] * len(s), 10**9 + 7
   for i, char in enumerate(s):
      ind = s.rfind(char, 0, i)
      dp[i] = 1 + sum(dp[:i]) % m if ind == -1 else sum(dp[ind:i]) % m
   return sum(dp) % m

s = "bab"
print(solve(s))

Đầu vào

"abcd", "abcdbcd"

Đầu ra

6