#include<bits/stdc++.h> #include "message.h" #include "poszukiwania.h" //#define DR if(1) using namespace std; vector<int> slowo; vector<int> itab;///tab do kmp int kmp(int n, int szu) { int i,t,wyn=0,dl=0; itab.push_back(0); // itab.push_back(0); for(i=1;i<n;i++) { while(dl>0&&slowo[dl]!=slowo[i]) dl=itab[dl-1]; if(slowo[dl]==slowo[i]) dl++; //printf("dl=%d\n" ,dl); if(dl==szu) wyn++; itab.push_back(dl); } return wyn; } /* int MyNodeId() { return 0; } int SeqLength() { return 11; } int SignalLength() { return 5; } int SignalAt(int a) { int sig[5]={1,2,3,2,1}; printf("%d " ,sig[a-1]); return sig[a-1]; } int SeqAt(int a) { int seq[11]={1,2,3,2,1,2,3,2,1,2}; return seq[a-1]; } */ int main() { int i,wyn,j,S,M,inst; inst=MyNodeId(); if(inst) return 0; S=(int)SignalLength(); M=(int)SeqLength(); //printf("%d %d\n",S,M); for(i=1;i<=S;i++) slowo.push_back((int)SignalAt(i)); slowo.push_back(-1); for(i=1;i<=M;i++) slowo.push_back((int)SeqAt(i)); // for(i=0;i<=S+M;i++) // printf("|%d|\n" ,slowo[i]); wyn=kmp(slowo.size(),S); // for(i=0;i) printf("%d\n",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 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 | #include<bits/stdc++.h> #include "message.h" #include "poszukiwania.h" //#define DR if(1) using namespace std; vector<int> slowo; vector<int> itab;///tab do kmp int kmp(int n, int szu) { int i,t,wyn=0,dl=0; itab.push_back(0); // itab.push_back(0); for(i=1;i<n;i++) { while(dl>0&&slowo[dl]!=slowo[i]) dl=itab[dl-1]; if(slowo[dl]==slowo[i]) dl++; //printf("dl=%d\n" ,dl); if(dl==szu) wyn++; itab.push_back(dl); } return wyn; } /* int MyNodeId() { return 0; } int SeqLength() { return 11; } int SignalLength() { return 5; } int SignalAt(int a) { int sig[5]={1,2,3,2,1}; printf("%d " ,sig[a-1]); return sig[a-1]; } int SeqAt(int a) { int seq[11]={1,2,3,2,1,2,3,2,1,2}; return seq[a-1]; } */ int main() { int i,wyn,j,S,M,inst; inst=MyNodeId(); if(inst) return 0; S=(int)SignalLength(); M=(int)SeqLength(); //printf("%d %d\n",S,M); for(i=1;i<=S;i++) slowo.push_back((int)SignalAt(i)); slowo.push_back(-1); for(i=1;i<=M;i++) slowo.push_back((int)SeqAt(i)); // for(i=0;i<=S+M;i++) // printf("|%d|\n" ,slowo[i]); wyn=kmp(slowo.size(),S); // for(i=0;i) printf("%d\n",wyn); return 0; } |