#include <bits/stdc++.h> #include "message.h" #include "poszukiwania.h" using namespace std; #define INF 1010000000 #define EPS 1E-12 #define MP make_pair #define ST first #define ND second #define SZ(x)((int)(x).size()) #define PB push_back #define ALL(x) x.begin(), x.end() #define REP(i,n) for(int i=0; i<(n); ++i) #define REPD(i,n) for(int i=(n)-1; i>=0; --i) #define FOR(i,a,n) for(LL i=(a); i<=(n); ++i) #define FORD(i,a,n) for(int i=(a); i>=(n); --i) #define FORE(i,a) for(__typeof((a).begin()) i=(a).begin();i!=(a).end();++i) #define D(x) cerr<<#x<<" = "<<x<<", "; #define DE(x) cerr<<#x<<" = "<<x<<endl; #define DE2(x,y) cerr<<x<<": "<<y<<endl; #define D2(t,a,b,n,m) {FOR(_i_, a, n){FOR(_j_, b, m)cerr<</*setw(3)*/" "<<t[_i_][_j_];cerr<<endl;}} #define B1(w) "("<<w<<")" #define B2(w,x) "("<<w<<","<<x<<")" #define B3(w,x,y) "("<<w<<","<<x<<","<<y<<")" #define B4(w,x,y,z) "("<<w<<","<<x<<","<<y<<","<<z<<")" typedef long long LL; typedef unsigned long long ULL; typedef unsigned int UI; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; typedef pair<double, double> PDD; inline bool eq(double a, double b) {return abs(a-b)<EPS;} template<class c1, class c2> ostream &operator <<(ostream &out, pair<c1, c2> p) {return out<<"("<<p.ST<<","<<p.ND<<")";} template<class c1> void DB(c1 _ts_, c1 _te_) {while(_ts_!=_te_)cerr<</*setw(3)*/" "<<*_ts_, _ts_++;cerr<<endl;} template<class c1> void DB(queue<c1> _q_) {while(!_q_.empty())cerr<</*setw(3)*/" "<<_q_.front(), _q_.pop();cerr<<endl;} template<class c1> void DB(stack<c1> _s_) {while(!_s_.empty())cerr<</*setw(3)*/" "<<_s_.top(), _s_.pop();cerr<<endl;} int main() { LL n = SignalLength(), m = SeqLength(); if(MyNodeId() > 0) return 0; vector<int> wz; REP(i, n) wz.PB(SignalAt(i + 1)); wz.PB(-1); REP(i, m) wz.PB(SeqAt(i + 1)); //// // DB(ALL(wz)); //// vector<int> pr(SZ(wz)); pr[0] = -1; int k = -1; int res = 0; FOR(i, 1, SZ(wz) - 1) { k = pr[i - 1]; while(k >= 0 && wz[k + 1] != wz[i]) k = pr[k]; if(wz[k + 1] == wz[i]) k++; pr[i] = k; if(k == n - 1) res++; } printf("%d\n", res); return 0; } /* 5 11 1 2 3 2 1 2 1 2 3 2 1 2 3 2 1 2 */
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 | #include <bits/stdc++.h> #include "message.h" #include "poszukiwania.h" using namespace std; #define INF 1010000000 #define EPS 1E-12 #define MP make_pair #define ST first #define ND second #define SZ(x)((int)(x).size()) #define PB push_back #define ALL(x) x.begin(), x.end() #define REP(i,n) for(int i=0; i<(n); ++i) #define REPD(i,n) for(int i=(n)-1; i>=0; --i) #define FOR(i,a,n) for(LL i=(a); i<=(n); ++i) #define FORD(i,a,n) for(int i=(a); i>=(n); --i) #define FORE(i,a) for(__typeof((a).begin()) i=(a).begin();i!=(a).end();++i) #define D(x) cerr<<#x<<" = "<<x<<", "; #define DE(x) cerr<<#x<<" = "<<x<<endl; #define DE2(x,y) cerr<<x<<": "<<y<<endl; #define D2(t,a,b,n,m) {FOR(_i_, a, n){FOR(_j_, b, m)cerr<</*setw(3)*/" "<<t[_i_][_j_];cerr<<endl;}} #define B1(w) "("<<w<<")" #define B2(w,x) "("<<w<<","<<x<<")" #define B3(w,x,y) "("<<w<<","<<x<<","<<y<<")" #define B4(w,x,y,z) "("<<w<<","<<x<<","<<y<<","<<z<<")" typedef long long LL; typedef unsigned long long ULL; typedef unsigned int UI; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; typedef pair<double, double> PDD; inline bool eq(double a, double b) {return abs(a-b)<EPS;} template<class c1, class c2> ostream &operator <<(ostream &out, pair<c1, c2> p) {return out<<"("<<p.ST<<","<<p.ND<<")";} template<class c1> void DB(c1 _ts_, c1 _te_) {while(_ts_!=_te_)cerr<</*setw(3)*/" "<<*_ts_, _ts_++;cerr<<endl;} template<class c1> void DB(queue<c1> _q_) {while(!_q_.empty())cerr<</*setw(3)*/" "<<_q_.front(), _q_.pop();cerr<<endl;} template<class c1> void DB(stack<c1> _s_) {while(!_s_.empty())cerr<</*setw(3)*/" "<<_s_.top(), _s_.pop();cerr<<endl;} int main() { LL n = SignalLength(), m = SeqLength(); if(MyNodeId() > 0) return 0; vector<int> wz; REP(i, n) wz.PB(SignalAt(i + 1)); wz.PB(-1); REP(i, m) wz.PB(SeqAt(i + 1)); //// // DB(ALL(wz)); //// vector<int> pr(SZ(wz)); pr[0] = -1; int k = -1; int res = 0; FOR(i, 1, SZ(wz) - 1) { k = pr[i - 1]; while(k >= 0 && wz[k + 1] != wz[i]) k = pr[k]; if(wz[k + 1] == wz[i]) k++; pr[i] = k; if(k == n - 1) res++; } printf("%d\n", res); return 0; } /* 5 11 1 2 3 2 1 2 1 2 3 2 1 2 3 2 1 2 */ |