Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- #define sz(s) (int)(s).size()
- #define all(s) s.begin(),s.end()
- void Speed() {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- }
- void solve() {
- int n, m, k; cin >> n >> m >> k;
- string s, t; cin >> s;
- vector<int> mx(n), cnt(n + 1);
- for(int i = 0; i < m; i++){
- cin >> t;
- assert(sz(t) == n);
- for(int j = n - 1; j >= 0; j--){
- cnt[j] = 0;
- if(t[j] == s[j]) cnt[j] = 1 + cnt[j + 1];
- if(cnt[j] >= k) mx[j] = max(mx[j], cnt[j]);
- }
- }
- vector<int> dp(n + 1);
- dp[n] = 1;
- for(int i = n - 1; i >= 0; i--){
- for(int len = k; len <= mx[i]; len++){
- dp[i] |= dp[i + len];
- }
- }
- cout << (dp[0] ? "YES\n" : "NO\n");
- }
- int main() {
- freopen("killua.in", "r", stdin);
- Speed();
- int tc = 1;
- //cin >> tc;
- while (tc--) {
- solve();
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment