#include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream> #include <vector> using namespace std; int* pi = nullptr; int *compute_prefix_function(int *pattern, int psize) { int k = -1; int i = 1; int *pi = (int*) malloc(sizeof(int)*psize); if (!pi) return NULL; pi[0] = k; for (i = 1; i < psize; i++) { while (k > -1 && pattern[k+1] != pattern[i]) k = pi[k]; if (pattern[i] == pattern[k+1]) k++; pi[i] = k; } return pi; } int kmp(int *target, int tsize, int *pattern, int psize) { int i; int k = -1; if (!pi) return -1; for (i = 0; i < tsize; i++) { while (k > -1 && pattern[k+1] != target[i]) k = pi[k]; if (target[i] == pattern[k+1]) k++; if (k == psize - 1) { return i-k; } } return -1; } int main() { int n, m; cin >> n >> m; vector< vector< int > > c( n ); for ( int i = 0; i < n; ++i ) { int k; cin >> k; c[ i ].resize( k ); for ( int j = 0; j < k; ++j ) { cin >> c[ i ][ j ]; --c[ i ][ j ]; } } vector< int > p( m ); for ( int i = 0; i < m; ++i ) { cin >> p[ i ]; --p[ i ]; } pi = compute_prefix_function( &p[ 0 ], p.size() ); const int LIMIT = 10000000; vector< int > t( LIMIT ); int ops = 0; t[ 0 ] = 0; int tSize = 1; int step = 1; while ( 1 ) { const int foundPos = kmp( &t[ 0 ], tSize, &p[ 0 ], p.size() ); if ( foundPos != -1 ) { cout << step; return 0; } int newSize = 0; for ( int i = 0; i < tSize; ++i ) { newSize += c[ t[ i ] ].size(); } ops += newSize; if ( newSize > LIMIT || ops > LIMIT ) { cout << -1; return 0; } int pos = newSize - 1; for ( int i = tSize - 1; i >= 0; --i ) { const int p = t[ i ]; const vector< int >& a = c[ p ]; for ( int j = a.size() - 1; j >= 0; --j, --pos ) { t[ pos ] = a[ j ]; } } tSize = newSize; ++step; } 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 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 | #include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream> #include <vector> using namespace std; int* pi = nullptr; int *compute_prefix_function(int *pattern, int psize) { int k = -1; int i = 1; int *pi = (int*) malloc(sizeof(int)*psize); if (!pi) return NULL; pi[0] = k; for (i = 1; i < psize; i++) { while (k > -1 && pattern[k+1] != pattern[i]) k = pi[k]; if (pattern[i] == pattern[k+1]) k++; pi[i] = k; } return pi; } int kmp(int *target, int tsize, int *pattern, int psize) { int i; int k = -1; if (!pi) return -1; for (i = 0; i < tsize; i++) { while (k > -1 && pattern[k+1] != target[i]) k = pi[k]; if (target[i] == pattern[k+1]) k++; if (k == psize - 1) { return i-k; } } return -1; } int main() { int n, m; cin >> n >> m; vector< vector< int > > c( n ); for ( int i = 0; i < n; ++i ) { int k; cin >> k; c[ i ].resize( k ); for ( int j = 0; j < k; ++j ) { cin >> c[ i ][ j ]; --c[ i ][ j ]; } } vector< int > p( m ); for ( int i = 0; i < m; ++i ) { cin >> p[ i ]; --p[ i ]; } pi = compute_prefix_function( &p[ 0 ], p.size() ); const int LIMIT = 10000000; vector< int > t( LIMIT ); int ops = 0; t[ 0 ] = 0; int tSize = 1; int step = 1; while ( 1 ) { const int foundPos = kmp( &t[ 0 ], tSize, &p[ 0 ], p.size() ); if ( foundPos != -1 ) { cout << step; return 0; } int newSize = 0; for ( int i = 0; i < tSize; ++i ) { newSize += c[ t[ i ] ].size(); } ops += newSize; if ( newSize > LIMIT || ops > LIMIT ) { cout << -1; return 0; } int pos = newSize - 1; for ( int i = tSize - 1; i >= 0; --i ) { const int p = t[ i ]; const vector< int >& a = c[ p ]; for ( int j = a.size() - 1; j >= 0; --j, --pos ) { t[ pos ] = a[ j ]; } } tSize = newSize; ++step; } return 0; } |