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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
// Potyczki Algorytmiczne 2015
// runda 5
// EKSplozja komórkowa
// Tomasz Pastusiak

#include <iostream>
#include <algorithm>
#include <functional>
#include <stack>
#include <set>
#include <cmath>
#include <vector>
#include <string>
#include <list>

using namespace std;

// types are numbered 1 ... n
#define MAX_TYPES 501
#define MAX_SEQ_LEN 1000
#define MAX_REPL_LEN 1001
#define MAX_BODY_LEN 32000000L

#define LL long long int

// replications[type][0] contains replication size(length)
int replications[MAX_TYPES][MAX_REPL_LEN];
int sequence[MAX_SEQ_LEN];

LL body0len = 0;
LL body1len = 0;
int body0[MAX_BODY_LEN];
int body1[MAX_BODY_LEN];

int p[MAX_SEQ_LEN + 1]; // prefix table

void KMPprep(int *wzo, int wzoLen){
	LL k = 0, q, m;
	k = 0;
	p[1] = 0;
	// wyznacz tablicę prefiksową
	for(q = 1; q != wzoLen; q++){
		while(k > 0 && wzo[k] != wzo[q]) k = p[k];
		if(wzo[k] == wzo[q]) k++;
		
		p[q + 1] = k;
	}
}

void KMP(int *str, LL strLen, int *wzo, LL wzoLen, void (*fun)(LL)){
	int k = 0, q, m;
	//m = q;
	m = wzoLen;
	k = 0;
	// przeszukujemy...
	for(q = 0; q != strLen ; q++){
		while(k > 0 && wzo[k] != str[q]) k = p[k];
		if(wzo[k] == str[q]) k++;
		
		if(m == k){
			fun(q - m + 1);
			k = p[k];
		}
	}
} // KMP

bool found = false;

void foundFunction(LL where){
	found = true;
}

int main(){
	ios_base::sync_with_stdio(false);
	
	int n,m;
	cin >> n >> m;
	
	for(int i=1; i<=n ; ++i){
		cin >> replications[i][0];
		for(int j=1; j<=replications[i][0] ; ++j){
			cin >> replications[i][j];
		}
	}
	
	for(int i=0; i<m; ++i){
		cin >> sequence[i];
	}
	
	// DATA LOADED
	// now apply BRUTE force
	// simulate evolution for some turns, every step check if sequence occurs
	// after many steps, assume that he'll never be mature(?)
	
	int time = 1;
	body0[body0len++] = 1;
	
	LL* currentBodyLenPtr = &body0len;
	LL* helperBodyLenPtr = &body1len;
	int* currentBody = body0;
	int* helperBody = body1;
	
	bool simulationStop = false;
	
	KMPprep(sequence, m);
	
	while( !simulationStop ){
		KMP(currentBody, *currentBodyLenPtr, sequence, m, foundFunction);
		if(found) break;
		
		*helperBodyLenPtr = 0;
		for(LL i=0; i<*currentBodyLenPtr ;++i){
			if(*helperBodyLenPtr >= MAX_BODY_LEN - 1000L){
				simulationStop = true;
				//cout << "Helper body len: " << (*helperBodyLenPtr) << " at time: " << time << endl;
				break;
			}
			int replicatingCell = currentBody[i];
			for(int j=1; j <= replications[replicatingCell][0] ;++j){
				helperBody[(*helperBodyLenPtr)++] = replications[replicatingCell][j];
			}
		} // for each replicating cell
		
		time++;
		swap(currentBody, helperBody);
		swap(currentBodyLenPtr, helperBodyLenPtr);
	}
	
	if(found) cout << time << endl;
	else cout << -1 << endl;
	
	return 0;
}