fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3.  
  4. using namespace std;
  5. const ll MOD = 1e9 + 7;
  6. const int N = 1e5 + 7;
  7. const int M = 1e3 + 7;
  8.  
  9. int n, m, k;
  10. string a, b;
  11. ll fact[M], hash_A[M], hash_B[111], cnt_B_2[N], dp[111][111], cnt[111][111];
  12.  
  13. void sub1() {
  14.     ll ans = 0;
  15.     for (int i = 1; i <= n - m + 1; i++) {
  16.         bool same = true;
  17.         for (int j = 1; j <= m; j++) {
  18.             if (a[i + j - 1] != b[j]) {
  19.                 same = false;
  20.                 break;
  21.             }
  22.         }
  23.         if (same == true) ans++;
  24.     }
  25.     cout << ans % MOD << '\n';
  26. }
  27.  
  28. ll get_Hash_A(int l, int r) {
  29.     return (hash_A[r] - hash_A[l - 1] * fact[r - l + 1] + MOD * MOD) % MOD;
  30. }
  31.  
  32. ll get_Hash_B(int l, int r) {
  33.     return (hash_B[r] - hash_B[l - 1] * fact[r - l + 1] + MOD * MOD) % MOD;
  34. }
  35.  
  36. void sub2() {
  37.     ll ans = 0, base = 313;
  38.     hash_A[0] = hash_B[0] = fact[0] = 1;
  39.     for (int i = 1; i <= n; i++) {
  40.         hash_A[i] = (hash_A[i - 1] * base + a[i] - 'a' + 1) % MOD;
  41.         fact[i] = (fact[i - 1] * base) % MOD;
  42.     }
  43.     for (int i = 1; i <= m; i++) {
  44.         hash_B[i] = (hash_B[i - 1] * base + b[i] - 'a' + 1) % MOD;
  45.     }
  46.     for (int len1 = 1; len1 < m; len1++) {
  47.         int len2 = m - len1;
  48.         ll hash_B_1 = get_Hash_B(1, len1), hash_B_2 = get_Hash_B(len1 + 1, m);
  49.         memset(cnt_B_2, 0, sizeof(cnt_B_2));
  50.         for (int i = n - len2 + 1; i >= 1; i--) {
  51.             cnt_B_2[i] = cnt_B_2[i + 1];
  52.             if (get_Hash_A(i, i + len2 - 1) == hash_B_2) cnt_B_2[i]++;
  53.         }
  54.         for (int i = 1; i <= n - len1 + 1;i++) {
  55.             if ((i + len1 <= n) && (get_Hash_A(i, i + len1 - 1) == hash_B_1)) {
  56.                 ans = (ans + cnt_B_2[i + len1]) % MOD;
  57.             }
  58.         }
  59.     }
  60.     cout << ans << '\n';
  61. }
  62.  
  63. void sub34() {
  64.     dp[0][0] = 1;
  65.     for (int i = 1; i <= n; i++) {
  66.         for (int j = m; j >= 1; j--) {
  67.             if (a[i] == b[j]) {
  68.                 for (int t = 1; t <= k; t++) {
  69.                     cnt[t][j] = (cnt[t][j - 1] + dp[t - 1][j - 1]) % MOD;
  70.                     dp[t][j] = (dp[t][j] + cnt[t][j]) % MOD;
  71.                 }
  72.             }else for (int t = 1; t <= k; t++) cnt[t][j] = 0;
  73.         }
  74.     }
  75.     cout << dp[k][m] << '\n';
  76. }
  77.  
  78. signed main() {
  79.     ios_base::sync_with_stdio(0);
  80.     cin.tie(0); cout.tie(0);
  81.  
  82.     freopen("CHONXAU.inp", "r", stdin);
  83.     freopen("CHONXAU.out", "w", stdout);
  84.  
  85.     cin >> n >> m >> k;
  86.     cin >> a >> b;
  87.     a = " " + a;
  88.     b = " " + b;
  89.     if ((k == 1) && (n <= 1000) && (m <= 100)) sub1();
  90.     else if ((k == 2) && (n <= 1000) && (m <= 100)) sub2();
  91.     else sub34();
  92.     return 0;
  93. }
  94.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FP17aq
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!