fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <map>
  6. #include <queue>
  7. #include <stack>
  8. #include <vector>
  9. #include <deque>
  10. #include <functional>
  11. #include <string>
  12. #include <iostream>
  13. #include <cctype>
  14. #include <set>
  15. #include <climits>
  16. #include <iomanip>
  17. #include <cassert>
  18.  
  19. using namespace std;
  20.  
  21. #define D(x)        cout<<#x " = "<<(x)<<endl
  22. #define un(x)       x.erase(unique(x.begin(),x.end()), x.end())
  23. #define sf(n)       scanf("%d", &n)
  24. #define sff(a,b)    scanf("%d %d", &a, &b)
  25. #define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
  26. #define pb          push_back
  27. #define pi          2*acos(0.0)
  28. #define mp          make_pair
  29. #define xx          first
  30. #define yy          second
  31. #define hp          (ll) 999983
  32. #define mx          100000
  33. #define mod         1000000007
  34. #define endl        '\n'
  35.  
  36. typedef long long int ll;
  37.  
  38. ll F[mx+7];
  39. vector<pair<int, char> > A, B;
  40. void failure_function( char *pattern, ll len ) {
  41.     F[0] = F[1] = 0;
  42.     ll i,j;
  43.     for( i=2; i<=len; i++ ) {
  44.         j = F[i-1];
  45.         while( 1 ) {
  46.             if( pattern[j] == pattern[i-1] ) {
  47.                 F[i] = j + 1;
  48.                 break;
  49.             }
  50.             if( j==0) {
  51.                 F[i] = 0;
  52.                 break;
  53.             }
  54.             j = F[j];
  55.         }
  56.     }
  57. }
  58.  
  59. ll KMP( char *text, ll len_t, char *pattern, ll len_p  ) {
  60.     failure_function( pattern, len_p );
  61.     ll i = 0,j = 0, ret = 0, h, k, m;
  62.     deque<ll> v;
  63.     while( j<len_t ) {
  64.         if( text[j] == pattern[i] ) {
  65.             i++;
  66.             j++;
  67.             v.pb(j - 1);
  68.             if( i == len_p ) {
  69.                 if(v.size() == 1) {
  70.                     cout << A[j - 1].first << " " << B[i - 1].first << endl;
  71.                     if(A[j - 1].first >= B[i - 1].first) {
  72.                         ret += A[j - 1].first - B[i - 1].first;
  73.                     }
  74.                     if(A[j - 1].first == B[i - 1].first) {
  75.                         ret ++;
  76.                     }
  77.                 } else {
  78.                     m = 0;
  79.                     for(h = 0; h < v.size(); h ++) {
  80.                         k = v[h];
  81.                         if(h == 0 || h == v.size() - 1) {
  82.                             if(A[k].first >= B[k].first) m ++;
  83.                             else break;
  84.                         } else if(A[k].first == B[k].first) m ++;
  85.                         else break;
  86.                         //cout << A[k].first << " " << B[k].first << endl;
  87.                     }
  88.                     if(m == len_p) {
  89.                         ret ++;
  90.                     }
  91.                 }
  92.             }
  93.         } else if( i > 0 ) i = F[i], v.clear();
  94.         else {
  95.             j++;
  96.             if(!v.empty()) v.pop_front();
  97.         }
  98.     }
  99.     return ret;
  100. }
  101.  
  102. int main() {
  103.     int i, j, k, n, m, l, a, b;
  104.     char t[mx + 10], s[mx + 10], ch;
  105.     sff(n, m);
  106.     for(i = 1, j = 0; i <= n; i ++) {
  107.         scanf("%d-%c", &l, &ch);
  108.         if(A.size()) {
  109.             if(A.back().second == ch) {
  110.                 A.back().first += l;
  111.                 continue;
  112.             }
  113.         }
  114.         A.pb(make_pair(l, ch));
  115.         t[j++] = ch;
  116.     }
  117.     t[j] = '\0';
  118.  
  119.     for(i = 1, j = 0; i <= m; i ++) {
  120.         scanf("%d-%c", &l, &ch);
  121.         if(B.size()) {
  122.             if(B.back().second == ch) {
  123.                 B.back().first += l;
  124.                 continue;
  125.             }
  126.         }
  127.         B.pb(make_pair(l, ch));
  128.         s[j++] = ch;
  129.     }
  130.     s[j++] = '\0';
  131.     a = strlen(t), b = strlen(s);
  132.     cout << s << " " << t << endl;
  133.     printf("%d\n", KMP(t, a, s, b));
  134. }
  135.  
Success #stdin #stdout 0s 4316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
 
0
https://ideone.com/yb5JCW
language:
C++14 (gcc 8.3)
created:
8 years 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!