#include <cstdio> #include <vector> #include "message.h" #include "poszukiwania.h" using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) typedef vector<int> VI; int main() { if (MyNodeId()) return 0; int m = SignalLength(); int j = 0; vector<int> pi(m + 1); FOR(k,1,m) { pi[k] = j; int a = SignalAt(k + 1); while (j && a != SignalAt(j + 1)) j = pi[j]; if (a == SignalAt(j + 1)) ++j; } pi[m] = j; int i = 0; j = 0; int n = SeqLength(); int r = 0; REP(i,n) { int a = SeqAt(i + 1); while (j && (j == m || a != SignalAt(j + 1))) j = pi[j]; if (a == SignalAt(j + 1)) ++j; if (j == m) ++r; } printf("%d\n", r); }
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 | #include <cstdio> #include <vector> #include "message.h" #include "poszukiwania.h" using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) typedef vector<int> VI; int main() { if (MyNodeId()) return 0; int m = SignalLength(); int j = 0; vector<int> pi(m + 1); FOR(k,1,m) { pi[k] = j; int a = SignalAt(k + 1); while (j && a != SignalAt(j + 1)) j = pi[j]; if (a == SignalAt(j + 1)) ++j; } pi[m] = j; int i = 0; j = 0; int n = SeqLength(); int r = 0; REP(i,n) { int a = SeqAt(i + 1); while (j && (j == m || a != SignalAt(j + 1))) j = pi[j]; if (a == SignalAt(j + 1)) ++j; if (j == m) ++r; } printf("%d\n", r); } |