#include "poszukiwania.h" #include "message.h" #include <algorithm> #include <iostream> #include <cstdio> using namespace std; const int MX = 14000000; const int STALA = 3000000; int P[MX], s[MX], roz = 0; int srch(vector<int> a) { roz = 1; long long M = SignalLength(); for (int i = 1; i <= M; ++ i) s[roz++] = SignalAt(i); s[roz++] = -1; for (int i = 0; i < a.size(); ++ i) s[roz++] = a[i]; // kmp z : http://was.zaa.mimuw.edu.pl/?q=node/6 // poczatek P[1]= 0; int t = P[1]; for (int i = 2; i < roz; i++) { // Niezmiennik: t=P[i-1] while (t > 0 && s[t + 1] != s[i]) t = P[t]; // poszukiwanie odpowiedniego prefikso-sufiksu if (s[t + 1] == s[i]) t++; P[i] = t; } // koniec int res = 0; for (int i = 1; i < roz; ++ i) if (P[i] == M) ++ res; return res; } vector<int> pos[1000]; int Result = 0; int main() { long long N = SeqLength(); long long M = SignalLength(); long long COMPS = NumberOfNodes(); long long myCOMP = MyNodeId(); long long BOSS = 0; if (M > N) { if (myCOMP == BOSS) puts("0"); return 0; } if (myCOMP == BOSS) { int ktoremu = 1; for (int i = 1; i <= N; i += STALA) { pos[ktoremu].push_back(i); ktoremu ++; if (ktoremu == COMPS) ktoremu = 1; } for (int i = 1; i < COMPS; ++ i) { PutInt(i, pos[i].size()); for (int j = 0; j < pos[i].size(); ++ j) PutInt(i, pos[i][j]); Send(i); } for (int i = 1; i < COMPS; ++ i) { Receive(i); Result += GetInt(i); } printf("%d\n", Result); } else { Receive(0); int x = GetInt(0), result = 0; for (int i = 1; i <= x; ++ i) { int Position = GetInt(0); vector<int> positions; for (int j = Position; j < Position + STALA + M - 1 && j <= N; ++ j) positions.push_back(SeqAt(j)); int x = srch(positions); result += x; } PutInt(0,result); Send(0); } 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 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 | #include "poszukiwania.h" #include "message.h" #include <algorithm> #include <iostream> #include <cstdio> using namespace std; const int MX = 14000000; const int STALA = 3000000; int P[MX], s[MX], roz = 0; int srch(vector<int> a) { roz = 1; long long M = SignalLength(); for (int i = 1; i <= M; ++ i) s[roz++] = SignalAt(i); s[roz++] = -1; for (int i = 0; i < a.size(); ++ i) s[roz++] = a[i]; // kmp z : http://was.zaa.mimuw.edu.pl/?q=node/6 // poczatek P[1]= 0; int t = P[1]; for (int i = 2; i < roz; i++) { // Niezmiennik: t=P[i-1] while (t > 0 && s[t + 1] != s[i]) t = P[t]; // poszukiwanie odpowiedniego prefikso-sufiksu if (s[t + 1] == s[i]) t++; P[i] = t; } // koniec int res = 0; for (int i = 1; i < roz; ++ i) if (P[i] == M) ++ res; return res; } vector<int> pos[1000]; int Result = 0; int main() { long long N = SeqLength(); long long M = SignalLength(); long long COMPS = NumberOfNodes(); long long myCOMP = MyNodeId(); long long BOSS = 0; if (M > N) { if (myCOMP == BOSS) puts("0"); return 0; } if (myCOMP == BOSS) { int ktoremu = 1; for (int i = 1; i <= N; i += STALA) { pos[ktoremu].push_back(i); ktoremu ++; if (ktoremu == COMPS) ktoremu = 1; } for (int i = 1; i < COMPS; ++ i) { PutInt(i, pos[i].size()); for (int j = 0; j < pos[i].size(); ++ j) PutInt(i, pos[i][j]); Send(i); } for (int i = 1; i < COMPS; ++ i) { Receive(i); Result += GetInt(i); } printf("%d\n", Result); } else { Receive(0); int x = GetInt(0), result = 0; for (int i = 1; i <= x; ++ i) { int Position = GetInt(0); vector<int> positions; for (int j = Position; j < Position + STALA + M - 1 && j <= N; ++ j) positions.push_back(SeqAt(j)); int x = srch(positions); result += x; } PutInt(0,result); Send(0); } return 0; } |