fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4.  
  5. const ll mod = 1e9 + 7;
  6. const int nmax = 100000 + 5;
  7.  
  8. ll n, m, k;
  9. string a, b;
  10.  
  11. /* ================= SUB 1 ================= */
  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) ans++;
  24.     }
  25.     cout << ans % mod << '\n';
  26. }
  27.  
  28. /* ================= SUB 2 ================= */
  29.  
  30. ll fact[nmax], hash_a[nmax], hash_b[nmax], cnt_b2[nmax];
  31. ll base = 313;
  32.  
  33. ll get_hash_a(ll l, ll r) {
  34.     return (hash_a[r] - hash_a[l - 1] * fact[r - l + 1] + mod * mod) % mod;
  35. }
  36.  
  37. ll get_hash_b(ll l, ll r) {
  38.     return (hash_b[r] - hash_b[l - 1] * fact[r - l + 1] + mod * mod) % mod;
  39. }
  40.  
  41. void sub2() {
  42.     ll ans = 0;
  43.     fact[0] = hash_a[0] = hash_b[0] = 1;
  44.  
  45.     for (int i = 1; i <= n; i++) {
  46.         hash_a[i] = (hash_a[i - 1] * base + a[i] - 'a' + 1) % mod;
  47.         fact[i] = (fact[i - 1] * base) % mod;
  48.     }
  49.  
  50.     for (int i = 1; i <= m; i++)
  51.         hash_b[i] = (hash_b[i - 1] * base + b[i] - 'a' + 1) % mod;
  52.  
  53.     for (int len1 = 1; len1 < m; len1++) {
  54.         int len2 = m - len1;
  55.         ll hash_b1 = get_hash_b(1, len1);
  56.         ll hash_b2 = get_hash_b(len1 + 1, m);
  57.  
  58.         memset(cnt_b2, 0, sizeof cnt_b2);
  59.  
  60.         for (int i = n - len2 + 1; i >= 1; i--) {
  61.             cnt_b2[i] = cnt_b2[i + 1];
  62.             if (get_hash_a(i, i + len2 - 1) == hash_b2)
  63.                 cnt_b2[i]++;
  64.         }
  65.  
  66.         for (int i = 1; i <= n - len1 + 1; i++) {
  67.             if (i + len1 <= n && get_hash_a(i, i + len1 - 1) == hash_b1)
  68.                 ans = (ans + cnt_b2[i + len1]) % mod;
  69.         }
  70.     }
  71.  
  72.     cout << ans << '\n';
  73. }
  74.  
  75. /* ================= SUB 3 ================= */
  76.  
  77. ll dp1[105][105], cnt1[105][105];
  78.  
  79. void sub3() {
  80.     dp1[0][0] = 1;
  81.  
  82.     for (int i = 1; i <= n; i++) {
  83.         for (int j = m; j >= 1; j--) {
  84.             if (a[i] == b[j]) {
  85.                 for (int t = 1; t <= k; t++) {
  86.                     cnt1[t][j] = (cnt1[t][j - 1] + dp1[t - 1][j - 1]) % mod;
  87.                     dp1[t][j] = (dp1[t][j] + cnt1[t][j]) % mod;
  88.                 }
  89.             } else for (int t = 1; t <= k; t++) cnt1[t][j] = 0;
  90.         }
  91.     }
  92.  
  93.     cout << dp1[k][m] << '\n';
  94. }
  95.  
  96. /* ================= SUB 4 ================= */
  97.  
  98. ll dp2[25][25], cnt2[25][25];
  99.  
  100. void sub4() {
  101.     dp2[0][0] = 1;
  102.  
  103.     for (int i = 1; i <= n; i++) {
  104.         for (int j = m; j >= 1; j--) {
  105.             if (a[i] == b[j]) {
  106.                 for (int t = 1; t <= k; t++) {
  107.                     cnt2[t][j] = cnt2[t][j - 1] + dp2[t - 1][j - 1];
  108.                     if (cnt2[t][j] >= mod) cnt2[t][j] -= mod;
  109.  
  110.                     dp2[t][j] = dp2[t][j] + cnt2[t][j];
  111.                     if (dp2[t][j] >= mod) dp2[t][j] -= mod;
  112.                 }
  113.             } else for (int t = 1; t <= k; t++) cnt2[t][j] = 0;
  114.         }
  115.     }
  116.  
  117.     cout << dp2[k][m] << '\n';
  118. }
  119.  
  120. int main() {
  121.     ios_base::sync_with_stdio(0);
  122.     cin.tie(0); cout.tie(0);
  123.  
  124.     cin >> n >> m >> k;
  125.     cin >> a >> b;
  126.     a = " " + a;
  127.     b = " " + b;
  128.  
  129.     if (k == 1 && n <= 1000 && m <= 100) sub1();
  130.     else if (k == 2 && n <= 1000 && m <= 100) sub2();
  131.     else if (k >= 3 && n <= 1000 && m <= 100) sub3();
  132.     else if (k >= 3 && n <= 100000 && m <= 20) sub4();
  133.  
  134.     return 0;
  135. }
  136.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/n9oris
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!