//Jan Omeljaniuk // #include <cstdio> #include <vector> #include <string> #include <stack> #include <queue> #include <list> #include <bitset> #include <cassert> #include <iostream> #include <algorithm> #define unm unsigned long long int #define nm long long int #define uint unsigned int using namespace std; #include "message.h" #include "poszukiwania.h" /* vector<long long> seq = {2,1,2,3,2,1,2,3,2,1,2}; vector<long long> sig = {1,2,3,2,1}; int MyNodeId(){ return 0; } long long SignalLength(){ return 5; } long long SeqLength() { return 11; } long long SignalAt(long long i) {return sig[i-1];} long long SeqAt(long long i) {return seq[i-1];} */ vector<uint> p; vector<uint> wzorzec; vector<uint> tekst; void pref_suf(vector<uint> &ps){ const uint sz = SignalLength() + 1; ps.resize(sz); uint j = 0; for(uint i = 2; i < sz; ++i){ while( j > 0 && SignalAt(j+1) != SignalAt(i) ) j = ps[j]; if( SignalAt(j+1) == SignalAt(i) ) ++j; ps[i] = j; } } uint kmp(vector<uint> &ps){ uint j = 0, res=0; const uint wzrsz = SignalLength() + 1; const uint txtsz = SeqLength() + 1; for(uint i = 1 ; i < txtsz ; ++i ) { while( j > 0 && SignalAt(j+1) != SeqAt(i)) j = ps[j]; if(SignalAt(j+1)==SeqAt(i)) j++; if(j==wzrsz-1){ j = ps[j]; ++res; } } return res; } int main(){ ios_base::sync_with_stdio(0); if(MyNodeId()==0) { //Single threading FTW! pref_suf(p); cout << kmp(p) << "\n"; } 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 | //Jan Omeljaniuk // #include <cstdio> #include <vector> #include <string> #include <stack> #include <queue> #include <list> #include <bitset> #include <cassert> #include <iostream> #include <algorithm> #define unm unsigned long long int #define nm long long int #define uint unsigned int using namespace std; #include "message.h" #include "poszukiwania.h" /* vector<long long> seq = {2,1,2,3,2,1,2,3,2,1,2}; vector<long long> sig = {1,2,3,2,1}; int MyNodeId(){ return 0; } long long SignalLength(){ return 5; } long long SeqLength() { return 11; } long long SignalAt(long long i) {return sig[i-1];} long long SeqAt(long long i) {return seq[i-1];} */ vector<uint> p; vector<uint> wzorzec; vector<uint> tekst; void pref_suf(vector<uint> &ps){ const uint sz = SignalLength() + 1; ps.resize(sz); uint j = 0; for(uint i = 2; i < sz; ++i){ while( j > 0 && SignalAt(j+1) != SignalAt(i) ) j = ps[j]; if( SignalAt(j+1) == SignalAt(i) ) ++j; ps[i] = j; } } uint kmp(vector<uint> &ps){ uint j = 0, res=0; const uint wzrsz = SignalLength() + 1; const uint txtsz = SeqLength() + 1; for(uint i = 1 ; i < txtsz ; ++i ) { while( j > 0 && SignalAt(j+1) != SeqAt(i)) j = ps[j]; if(SignalAt(j+1)==SeqAt(i)) j++; if(j==wzrsz-1){ j = ps[j]; ++res; } } return res; } int main(){ ios_base::sync_with_stdio(0); if(MyNodeId()==0) { //Single threading FTW! pref_suf(p); cout << kmp(p) << "\n"; } return 0; } |