Chương trình đếm số chuỗi con duy nhất của một chuỗi trong C ++

Giả sử chúng ta có một chuỗi s, chúng ta phải tìm số lượng các dãy con duy nhất không rỗng của s. Nếu câu trả lời là rất lớn thì sửa đổi kết quả bằng 10 ^ 9 + 7.

Vì vậy, nếu đầu vào là s =​​"xxy", thì đầu ra sẽ là 5, vì có năm dãy con:"x", "xx", "xy", "y" và "xxy".

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

• m:=10 ^ 9 + 7

• n:=kích thước của s

• Xác định một bảng mảng có kích thước 26

• res:=0

• để khởi tạo i:=1, khi i <=n, cập nhật (tăng i lên 1), do−

  • c:=s [i - 1] - ASCII của 'a'

  • curr:=(res + 1 - table [c] + m) mod m

  • res:=(res + curr) mod m

  • table [c]:=(table [c] + curr) mod m

• trả lại res

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

Ví dụ

#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
int solve(string s) {
   int n = s.size();
   vector<int> table(26);
   long long res = 0;
   for (int i = 1; i <= n; ++i) {
      int c = s[i − 1] − 'a';
      int curr = (res + 1 − table[c] + m) % m;
      res = (res + curr) % m;
      table[c] = (table[c] + curr) % m;
   }
   return res;
}
int main(){
   string s = "xxy";
   cout << solve(s);
}

Đầu vào

"xxy"

Đầu ra

5