#include "poszukiwania.h" #include "message.h" #include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { if( MyNodeId() == 0 ){ long long n = SeqLength(); long long m = SignalLength(); vector<char> seq(n); for(int i=0; i<n; i++) seq[i] = SeqAt(i+1); vector<char> signal(m); for(int i=0; i<m; i++) signal[i] = SignalAt(i+1); vector<int> pref(m+1); int p = pref[0] = -1; for(int i=1; i<=m; i++){ while( p>-1 && signal[p]!=signal[i-1] ) p=pref[p]; pref[i]=++p; } int wyn = p = 0; for(int i=0; i<n; i++){ while( p>-1 && signal[p]!=seq[i] ) p=pref[p]; if( ++p==m ){ wyn++; p=pref[p]; } } cout<<wyn; } 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 | #include "poszukiwania.h" #include "message.h" #include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { if( MyNodeId() == 0 ){ long long n = SeqLength(); long long m = SignalLength(); vector<char> seq(n); for(int i=0; i<n; i++) seq[i] = SeqAt(i+1); vector<char> signal(m); for(int i=0; i<m; i++) signal[i] = SignalAt(i+1); vector<int> pref(m+1); int p = pref[0] = -1; for(int i=1; i<=m; i++){ while( p>-1 && signal[p]!=signal[i-1] ) p=pref[p]; pref[i]=++p; } int wyn = p = 0; for(int i=0; i<n; i++){ while( p>-1 && signal[p]!=seq[i] ) p=pref[p]; if( ++p==m ){ wyn++; p=pref[p]; } } cout<<wyn; } return 0; } |