KOI 지역본선 2013 고등부, no.5 바이러스 September 30, 2013

#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int n,k;
int m[111];
vector<int> v[111];
void calculate_pi(vector<int>& pi,const vector<int>& str){
    pi[0] = -1;
    int j = -1;
    for ( int i = 1 ; i < str.size() ; i++ ) {
        while ( j >= 0 && str[i] != str[j+1] ) j = pi[j];
        if ( str[i] == str[j+1] )
            pi[i] = ++j;
        else
            pi[i] = -1;
    }
}
bool match(vector<int> text,vector<int> pattern,vector<int> pi) {
    int j = -1;
    for ( int i = 0 ; i < text.size() ; i++ ) {
        while ( j >= 0 && text[i] != pattern[j+1]) j = pi[j];
        if ( text[i] == pattern[j+1] ) {
            j++;
            if ( j+1 == k ) {
                return true;
                j = pi[j];
            }
        }
    }
    return false;
}
bool go(int now) {
    vector<int> pi(v[0].size()-now);
    vector<int> __v;
    for ( int i = now ; i < v[0].size() ; i++ )
        __v.push_back(v[0][i]);
    calculate_pi(pi,__v);
    for ( int i = 1 ; i < n ; i++ ) {
        if ( !match(v[i],__v,pi) ) {
            reverse(v[i].begin(),v[i].end());
            if ( !match(v[i],__v,pi) )
                return false;
        }
    }
    return true;
}
int main() {
    scanf("%d%d",&n,&k);
    for ( int i = 0 ; i < n ; i++ ) {
        scanf("%d",&m[i]);
        for ( int j = 0 ; j < m[i] ; j++ ) {
            int t;
            scanf("%d",&t);
            v[i].push_back(t);
        }
    }
    bool ok = true;
    for ( int i = 0 ; i <= v[0].size()-k ; i++ ) {
        ok = go(i);
        if ( ok ) {
            printf("YES\n");
            return 0;
        }
    }
    ok = true;
    reverse(v[0].begin(),v[0].end());
    for ( int i = 0 ; i <=v[0].size()-k ; i++ ) {
        ok = go(i);
        if ( ok ) {
            printf("YES\n");
            return 0;
        }
    }
    printf("NO\n");
    return 0;
}