fork download
copy 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3. //Suffix array, dp
  4. #define NeOWami signed
  5. #define ft first
  6. #define sc second
  7. #define int long long
  8. const int MOD = 1e9;
  9. const int N = 2e5 + 5;
  10. const int BASE = 31;
  11. char base = char((int)'A' - 1);
  12. string a, b, s;
  13. int n, m, sz;
  14. int POW[N], Rhash[N], sa[N];
  15. int max_len[N], dp[N], ps[N];
  16.  
  17. int getRhash (int i, int len) {
  18.     return (Rhash[i] - Rhash[i + len] * POW[len]);
  19. }
  20. inline bool sufCmp(int i, int j) {
  21.     int lo = 1, hi = min(sz - i, sz - j);
  22.     while (lo <= hi) {
  23.         int mid = (lo + hi) >> 1;
  24.         if (getRhash(i, mid) == getRhash(j, mid)) lo = mid + 1;
  25.         else hi = mid - 1;
  26.     }
  27.     return s[i + hi] < s[j + hi];
  28. }
  29. void build_Suffix_Array() {
  30.     sz = n + m + 1;
  31.     s = a + base + b;
  32.     Rhash[sz] = 0;
  33.     for (int i = sz - 1; i >= 0; --i) {
  34.         Rhash[i] = Rhash[i + 1] * BASE + s[i] - base + 1;
  35.         sa[i] = i;
  36.     }
  37.     stable_sort(sa, sa + sz, sufCmp);
  38. }
  39.  
  40. int getlen(int i, int j) {
  41.     int l = 1, r = sz - j, ans = 0;
  42.     while(l <= r) {
  43.         int mid = l + r >> 1;
  44.         if (getRhash(i, mid) ==  getRhash(j, mid)) {
  45.             ans = mid;
  46.             l = mid + 1;
  47.         }
  48.         else r = mid - 1;
  49.     } 
  50.     return ans;
  51. }
  52. void progess() {
  53.     int idA = -1, idB = -1;
  54.     for (int i = 0; i < sz; i++) {
  55.         if (sa[i] < n) idA = sa[i];
  56.         if (sa[i] > n) idB = sa[i];
  57.         if (idA != -1 && idB != -1) max_len[idA + 1] = max(max_len[idA + 1], getlen(idA, idB));
  58.     }
  59.     idA = -1, idB = -1;
  60.     for (int i = sz - 1; i >= 0; i--) {
  61.         if (sa[i] < n) idA = sa[i];
  62.         if (sa[i] > n) idB = sa[i];
  63.         if (idA != -1 && idB != -1) max_len[idA + 1] = max(max_len[idA + 1], getlen(idA, idB));
  64.     }
  65. }
  66. int val(int i) {
  67.     if (i < 0) return 0;
  68.     return ps[i];
  69. }
  70. NeOWami main() {
  71.     cin.tie(NULL)->sync_with_stdio(false);
  72.     if(ifstream("STRGCUT.inp")) {
  73.         freopen("STRGCUT.inp", "r", stdin);
  74.         freopen("STRGCUT.out", "w", stdout);
  75.     }
  76.     POW[0] = 1; for (int i = 1; i < N; i++) POW[i] = POW[i - 1] * BASE;
  77.     cin >> a >> b;
  78.     n = a.size(); m = b.size();
  79.     build_Suffix_Array();
  80.     progess();
  81.     reverse(max_len + 1, max_len + n + 1);
  82.     dp[0] = ps[0] = 1;
  83.     for (int i = 1; i <= n; i++) {
  84.         dp[i] = (val(i - 1) - val(i - max_len[i] - 1) + MOD) % MOD;
  85.         ps[i] = (ps[i - 1] + dp[i]) % MOD;
  86.     }
  87.     cout << dp[n];
  88.     return 0;
  89. }
Success #stdin #stdout 0.01s 9036KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/R1li4H
language:
C++14 (gcc 8.3)
created:
1 day 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!