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

Giả sử ta có chuỗi s, ta phải tìm số dãy con không rỗng duy nhất của s. Nếu kết quả quá lớn, lấy modulo 10^9 + 7.

Ví dụ: s = "xxy", đầu ra = 5, vì có 5 dãy con: "x", "xx", "xy", "y", "xxy".

Để giải quyết, ta làm theo các bước:

• m := 10^9 + 7.
• n := độ dài s.
• Định nghĩa mảng table kích thước 26.
• res := 0.
• for i := 1; i <= n; ++i:
  • c := s[i-1] - 'a'.
  • curr := (res + 1 - table[c] + m) % m.
  • res := (res + curr) % m.
  • table[c] := (table[c] + curr) % m.
• Trả về res.

Xem triển khai dưới đây:

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