#include <iostream> #include "message.h" #include "poszukiwania.h" using namespace std; // 2G / 100 instancji = 20M char pasuje[20000001]; // 20M int P [10000001]; // 4*10M = 40M int wzorzec[10000001]; // 4*10M = 40M int instancja,dx,skok,krata; int M,S; bool porownajWT(int w_i,int t_i){ //return (SignalAt(krata*w_i+dx+1)==SeqAt(instancja+krata*t_i+dx+1)); // ???? return (wzorzec[w_i]==SeqAt(instancja+krata*t_i+dx+1)); } bool porownajWW(int w_i,int w2_i){ //return (SignalAt(krata*w_i+dx+1)==SignalAt(krata*w2_i+dx+1)); // ???? return (wzorzec[w_i]==wzorzec[w2_i]); } int sufit(int x){ int y=x/krata; if(x>y*krata) return y+1; else return y; } int main() { krata=NumberOfNodes(); instancja=MyNodeId(); //krata=100; //instancja=0; int ile_w_sumie=0; M = SeqLength(); S = SignalLength(); //for(instancja=0;instancja<krata;instancja++){ int m,n,i,j,t; for(i=0;i<=20000000;i++) pasuje[i]=0; for(dx=0;dx<krata;dx++){ n=sufit(M-dx-instancja); m=sufit(S-dx); for(i=0;i<m;i++) wzorzec[i]=SignalAt(krata*i+dx+1); if(dx==0) for(j=0;j<=n-m;j++) pasuje[j]=1; //obliczenie tablicy P P[0]=0; P[1]=0; t=0; for (j=2; j<=m; j++){ while ((t>0)&&(!porownajWW(t,j-1))) t=P[t]; if (porownajWW(t,j-1)) t++; P[j]=t; } //algorytm KMP i=1; j=0; //cout << endl << "dx "<<dx<<" "; while (i<=n-m+1){ // j ile sie pokrylo ostatnio j=P[j];// dlugosc ramki ostatnio pokrywajacej sie while((j<m)&&(porownajWT(j,i+j-1))) j++; if (j==m){ //cout << " pas "<<i-1<<" "; if((pasuje[i-1]==1)) pasuje[i-1]=2; } i=i+max(1,j-P[j]); } for(j=0;j<=n-m;j++) if(pasuje[j]==2) pasuje[j]=1; else pasuje[j]=0; } int ile=0; // podliczyc u siebie for(j=0;j<=20000000;j++) if(pasuje[j]==1){ if(instancja+j*krata+S<=M)ile++; } if (instancja > 0){ // wyslac ile do 0 PutInt(0,ile); Send(0); }else{ // jesli 0 to odebrac od pozostalych i dodac do ile for(i=1;i<krata;i++){ Receive(i); ile+=GetInt(i); } cout << ile; } //} 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 | #include <iostream> #include "message.h" #include "poszukiwania.h" using namespace std; // 2G / 100 instancji = 20M char pasuje[20000001]; // 20M int P [10000001]; // 4*10M = 40M int wzorzec[10000001]; // 4*10M = 40M int instancja,dx,skok,krata; int M,S; bool porownajWT(int w_i,int t_i){ //return (SignalAt(krata*w_i+dx+1)==SeqAt(instancja+krata*t_i+dx+1)); // ???? return (wzorzec[w_i]==SeqAt(instancja+krata*t_i+dx+1)); } bool porownajWW(int w_i,int w2_i){ //return (SignalAt(krata*w_i+dx+1)==SignalAt(krata*w2_i+dx+1)); // ???? return (wzorzec[w_i]==wzorzec[w2_i]); } int sufit(int x){ int y=x/krata; if(x>y*krata) return y+1; else return y; } int main() { krata=NumberOfNodes(); instancja=MyNodeId(); //krata=100; //instancja=0; int ile_w_sumie=0; M = SeqLength(); S = SignalLength(); //for(instancja=0;instancja<krata;instancja++){ int m,n,i,j,t; for(i=0;i<=20000000;i++) pasuje[i]=0; for(dx=0;dx<krata;dx++){ n=sufit(M-dx-instancja); m=sufit(S-dx); for(i=0;i<m;i++) wzorzec[i]=SignalAt(krata*i+dx+1); if(dx==0) for(j=0;j<=n-m;j++) pasuje[j]=1; //obliczenie tablicy P P[0]=0; P[1]=0; t=0; for (j=2; j<=m; j++){ while ((t>0)&&(!porownajWW(t,j-1))) t=P[t]; if (porownajWW(t,j-1)) t++; P[j]=t; } //algorytm KMP i=1; j=0; //cout << endl << "dx "<<dx<<" "; while (i<=n-m+1){ // j ile sie pokrylo ostatnio j=P[j];// dlugosc ramki ostatnio pokrywajacej sie while((j<m)&&(porownajWT(j,i+j-1))) j++; if (j==m){ //cout << " pas "<<i-1<<" "; if((pasuje[i-1]==1)) pasuje[i-1]=2; } i=i+max(1,j-P[j]); } for(j=0;j<=n-m;j++) if(pasuje[j]==2) pasuje[j]=1; else pasuje[j]=0; } int ile=0; // podliczyc u siebie for(j=0;j<=20000000;j++) if(pasuje[j]==1){ if(instancja+j*krata+S<=M)ile++; } if (instancja > 0){ // wyslac ile do 0 PutInt(0,ile); Send(0); }else{ // jesli 0 to odebrac od pozostalych i dodac do ile for(i=1;i<krata;i++){ Receive(i); ile+=GetInt(i); } cout << ile; } //} return 0; } |