#include <cstdio> #include <iostream> #include <algorithm> #include <string> #include <sstream> #include <vector> #include <list> #include <set> #include <map> #include "poszukiwania.h" #include "message.h" using namespace std; typedef vector<int> VI; typedef vector<VI> VVI; typedef pair<int, int> PI; typedef vector<PI> VPI; typedef long long LL; typedef vector<LL> VLL; #define FOR(x, b, e) for(int x = b; x <= (e); ++x) #define FORD(x, b, e) for(int x = b; x >= (e); --x) #define REP(x, n) for(int x = 0; x < (n); ++x) #define VAR(v, n) __typeof(n) v = (n) #define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define ALL(c) (c).begin(), (c).end() #define SIZE(x) ((int)(x).size()) #define PB push_back #define MP make_pair #define ST first #define ND second const int INF = 1000000001; const double EPS = 10e-9; int KMP(vector<int>& str, vector<int>& wzo) { #define KMPH(z) while(k > 0 && wzo[k] != z[q]) k = p[k]; \ if(wzo[k] == z[q]) k++; int k = 0, q, m, result = 0; VI p(SIZE(wzo) + 1); p[1] = 0; for(q = 1; wzo[q]; q++) { KMPH(wzo); p[q + 1] = k; } m = q; k = 0; for(q = 0; str[q]; q++) { KMPH(str); if(m == k) { ++result; k = p[k]; } } return result; } int main() { if (MyNodeId() == 0) { int s = SignalLength(); int m = SeqLength(); vector<int> signal(s); vector<int> sequence(m); for (int i = 0; i < s; ++i) { signal[i] = SignalAt(i + 1); } for (int i = 0; i < m; ++i) { sequence[i] = SeqAt(i + 1); } printf("%d\n", KMP(sequence, signal)); } return 0; }
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 | #include <cstdio> #include <iostream> #include <algorithm> #include <string> #include <sstream> #include <vector> #include <list> #include <set> #include <map> #include "poszukiwania.h" #include "message.h" using namespace std; typedef vector<int> VI; typedef vector<VI> VVI; typedef pair<int, int> PI; typedef vector<PI> VPI; typedef long long LL; typedef vector<LL> VLL; #define FOR(x, b, e) for(int x = b; x <= (e); ++x) #define FORD(x, b, e) for(int x = b; x >= (e); --x) #define REP(x, n) for(int x = 0; x < (n); ++x) #define VAR(v, n) __typeof(n) v = (n) #define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define ALL(c) (c).begin(), (c).end() #define SIZE(x) ((int)(x).size()) #define PB push_back #define MP make_pair #define ST first #define ND second const int INF = 1000000001; const double EPS = 10e-9; int KMP(vector<int>& str, vector<int>& wzo) { #define KMPH(z) while(k > 0 && wzo[k] != z[q]) k = p[k]; \ if(wzo[k] == z[q]) k++; int k = 0, q, m, result = 0; VI p(SIZE(wzo) + 1); p[1] = 0; for(q = 1; wzo[q]; q++) { KMPH(wzo); p[q + 1] = k; } m = q; k = 0; for(q = 0; str[q]; q++) { KMPH(str); if(m == k) { ++result; k = p[k]; } } return result; } int main() { if (MyNodeId() == 0) { int s = SignalLength(); int m = SeqLength(); vector<int> signal(s); vector<int> sequence(m); for (int i = 0; i < s; ++i) { signal[i] = SignalAt(i + 1); } for (int i = 0; i < m; ++i) { sequence[i] = SeqAt(i + 1); } printf("%d\n", KMP(sequence, signal)); } return 0; } |