#include "poszukiwania.h" #include "message.h" #include <iostream> #include <vector> using namespace std; int n1,n2,a,t,res; vector<int> tab; int tekst(const int &ile){ // printf("ile: %d\n",ile); if(ile == 0)return (-1); else if(ile == (n1 + 1))return (-2); else if(ile <= n1)return SignalAt(ile); else return SeqAt(ile - n1 - 1); } void kmp(){ //tekst = $sig#seq tab[0] = tab[1] = t = 0; for(int i = 2; i < (n1 + n2 + 2); i++){ a = (t + 1); while(t > 0 && tekst(a) != tekst(i)){ t = tab[t]; a = (t + 1); } if(tekst(a) == tekst(i))t++; if(i <= n1)tab[i] = t; if(t == n1)res++; } } int main() { if(MyNodeId() == 0){ n1 = SignalLength(); n2 = SeqLength(); tab.resize(n1 + 3); kmp(); cout<<res<<endl; } }
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 | #include "poszukiwania.h" #include "message.h" #include <iostream> #include <vector> using namespace std; int n1,n2,a,t,res; vector<int> tab; int tekst(const int &ile){ // printf("ile: %d\n",ile); if(ile == 0)return (-1); else if(ile == (n1 + 1))return (-2); else if(ile <= n1)return SignalAt(ile); else return SeqAt(ile - n1 - 1); } void kmp(){ //tekst = $sig#seq tab[0] = tab[1] = t = 0; for(int i = 2; i < (n1 + n2 + 2); i++){ a = (t + 1); while(t > 0 && tekst(a) != tekst(i)){ t = tab[t]; a = (t + 1); } if(tekst(a) == tekst(i))t++; if(i <= n1)tab[i] = t; if(t == n1)res++; } } int main() { if(MyNodeId() == 0){ n1 = SignalLength(); n2 = SeqLength(); tab.resize(n1 + 3); kmp(); cout<<res<<endl; } } |