#include<bits/stdc++.h> using namespace std; vector<int>powinno; vector<int>zmiana[507]; vector<int>teraz; vector<int>bedzie; int odp[5000007]; bool KMP(int M) { int t = 0; for (int i = M+1;i < bedzie.size();i++) { while (bedzie[t] != bedzie[i] && t != 0) t = odp[t]; if (bedzie[t] == bedzie[i]) t++; odp[i] = t; if (t == M) return true; } return false; } int main() { int N,M; scanf("%d%d",&N,&M); int a,b; for (int i = 1;i <= N;i++) { scanf("%d",&a); while (a--) { scanf("%d",&b); zmiana[i].push_back(b); } } for (int i = 0;i < M;i++) { scanf("%d",&a); powinno.push_back(a); } powinno.push_back(-1); teraz.push_back(1); int il = 1; if (M == 1 && powinno[0] == 1) { printf("1\n"); return 0; } bedzie = powinno; bedzie.push_back(1); while (il < 1000) { il++; teraz = bedzie; bedzie = powinno; for (int i = M+1;i < teraz.size();i++) { for (int w = 0;w < zmiana[teraz[i]].size();w++) { bedzie.push_back(zmiana[teraz[i]][w]); } } if (KMP(M)) { printf("%d\n",il); return 0; } } if (il == 1000) printf("-1"); 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 | #include<bits/stdc++.h> using namespace std; vector<int>powinno; vector<int>zmiana[507]; vector<int>teraz; vector<int>bedzie; int odp[5000007]; bool KMP(int M) { int t = 0; for (int i = M+1;i < bedzie.size();i++) { while (bedzie[t] != bedzie[i] && t != 0) t = odp[t]; if (bedzie[t] == bedzie[i]) t++; odp[i] = t; if (t == M) return true; } return false; } int main() { int N,M; scanf("%d%d",&N,&M); int a,b; for (int i = 1;i <= N;i++) { scanf("%d",&a); while (a--) { scanf("%d",&b); zmiana[i].push_back(b); } } for (int i = 0;i < M;i++) { scanf("%d",&a); powinno.push_back(a); } powinno.push_back(-1); teraz.push_back(1); int il = 1; if (M == 1 && powinno[0] == 1) { printf("1\n"); return 0; } bedzie = powinno; bedzie.push_back(1); while (il < 1000) { il++; teraz = bedzie; bedzie = powinno; for (int i = M+1;i < teraz.size();i++) { for (int w = 0;w < zmiana[teraz[i]].size();w++) { bedzie.push_back(zmiana[teraz[i]][w]); } } if (KMP(M)) { printf("%d\n",il); return 0; } } if (il == 1000) printf("-1"); return 0; } |