#include <iostream> #include <vector> using namespace std; bool kmp3(vector<int> *bajtkom, vector<int> *maturity){ vector<int> T; for(int i=0 ; bajtkom->at(i)!=-1 ; i++) { if( bajtkom->at(i) == maturity->at(0) ) { T.push_back(i); } } for(int i=0, k=0, m=T[k] ; (m+i) <= bajtkom->size() && k < T.size(); i++ ) { if( maturity->at(i) != bajtkom->at(m+i) ) { m=T[++k]; i=0; } if( i == maturity->size()-1 ) { return true; } } return false; } int main() { int varietesNumber = 0; int sequenceLength = 0; scanf("%d", &varietesNumber); scanf("%d", &sequenceLength); vector<vector<int>> varietes; for (int i = 0; i < varietesNumber; i++) { int sequenceCount = 0; scanf("%d", &sequenceCount); vector<int> seqs; for (int j = 0; j < sequenceCount; j++) { int seq; scanf("%d", &seq); seqs.push_back(seq - 1); } varietes.push_back(seqs); } vector<int> *maturity = new vector<int>(); for (int k = 0; k < sequenceLength; k++) { int mat; scanf("%d", &mat); maturity->push_back(mat - 1); } vector<int> *bajtkomOld = new vector<int>(); bajtkomOld->push_back(0); bool match = false; int counter = 1; int max_count = 3000000; int max_count_add = 0; while (!match) { vector<int> *bajtkomNew = new vector<int>(); for (int i = 0; i < bajtkomOld->size(); ++i) { for (int j = 0; j < varietes[bajtkomOld->at(i)].size(); ++j) { bajtkomNew->push_back(varietes[bajtkomOld->at(i)][j]); } } bajtkomOld = bajtkomNew; bajtkomOld->push_back(-1); counter++; match = kmp3(bajtkomOld, maturity); max_count_add = max_count_add + bajtkomOld->size(); if(max_count_add > max_count){ counter = -1; break; } } printf("%d", counter); 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 | #include <iostream> #include <vector> using namespace std; bool kmp3(vector<int> *bajtkom, vector<int> *maturity){ vector<int> T; for(int i=0 ; bajtkom->at(i)!=-1 ; i++) { if( bajtkom->at(i) == maturity->at(0) ) { T.push_back(i); } } for(int i=0, k=0, m=T[k] ; (m+i) <= bajtkom->size() && k < T.size(); i++ ) { if( maturity->at(i) != bajtkom->at(m+i) ) { m=T[++k]; i=0; } if( i == maturity->size()-1 ) { return true; } } return false; } int main() { int varietesNumber = 0; int sequenceLength = 0; scanf("%d", &varietesNumber); scanf("%d", &sequenceLength); vector<vector<int>> varietes; for (int i = 0; i < varietesNumber; i++) { int sequenceCount = 0; scanf("%d", &sequenceCount); vector<int> seqs; for (int j = 0; j < sequenceCount; j++) { int seq; scanf("%d", &seq); seqs.push_back(seq - 1); } varietes.push_back(seqs); } vector<int> *maturity = new vector<int>(); for (int k = 0; k < sequenceLength; k++) { int mat; scanf("%d", &mat); maturity->push_back(mat - 1); } vector<int> *bajtkomOld = new vector<int>(); bajtkomOld->push_back(0); bool match = false; int counter = 1; int max_count = 3000000; int max_count_add = 0; while (!match) { vector<int> *bajtkomNew = new vector<int>(); for (int i = 0; i < bajtkomOld->size(); ++i) { for (int j = 0; j < varietes[bajtkomOld->at(i)].size(); ++j) { bajtkomNew->push_back(varietes[bajtkomOld->at(i)][j]); } } bajtkomOld = bajtkomNew; bajtkomOld->push_back(-1); counter++; match = kmp3(bajtkomOld, maturity); max_count_add = max_count_add + bajtkomOld->size(); if(max_count_add > max_count){ counter = -1; break; } } printf("%d", counter); return 0; } |