Advertisement
Guest User

Untitled

a guest
Jul 21st, 2019
302
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.82 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstring>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. int n, m;
  9. long long sol;
  10.  
  11. char a[2000005], b[2000005];
  12. int pi[2000005], mx[2000005];
  13.  
  14. int main() {
  15.   cin >> (a + 1) >> (b + 1);
  16.   n = strlen(a + 1); m = strlen(b + 1);
  17.   int q = 0;
  18.   for(int i = 2; i <= n; i++) {
  19.     while(q && a[q + 1]  != a[i])
  20.       q = pi[q];
  21.     if(a[q + 1] == a[i])
  22.       q++;
  23.     pi[i] = q;
  24.   }
  25.   q = 0;
  26.   for(int i = 1; i <= m; i++) {
  27.     while(q && a[q + 1] != b[i])
  28.       q = pi[q];
  29.     if(a[q + 1] == b[i])
  30.       q++;
  31.     int tmp = q;
  32.     while(tmp) {
  33.       mx[i - tmp + 1] = max(mx[i - tmp + 1], tmp);
  34.       tmp = pi[tmp];
  35.     }
  36.   }
  37.   for(int i = 1; i <= m; i++)
  38.     sol += 1LL * (mx[i] + 1) * mx[i] / 2 + 1LL * mx[i] * (m - i - mx[i] + 1);
  39.   cout << sol;
  40.   return 0;
  41. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement