AhmedAshraff

Untitled

Jun 17th, 2025
37
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.99 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5. #define sz(s) (int)(s).size()
  6. #define all(s) s.begin(),s.end()
  7.  
  8. void Speed() {
  9.     ios_base::sync_with_stdio(false);
  10.     cin.tie(NULL);
  11. }
  12.  
  13. void solve() {
  14.     int n, m, k; cin >> n >> m >> k;
  15.     string s, t; cin >> s;
  16.     vector<int> mx(n), cnt(n + 1);
  17.     for(int i = 0; i < m; i++){
  18.         cin >> t;
  19.         assert(sz(t) == n);
  20.         for(int j = n - 1; j >= 0; j--){
  21.             cnt[j] = 0;
  22.             if(t[j] == s[j]) cnt[j] = 1 + cnt[j + 1];
  23.             if(cnt[j] >= k) mx[j] = max(mx[j], cnt[j]);
  24.         }
  25.     }
  26.    
  27.     vector<int> dp(n + 1);
  28.     dp[n] = 1;
  29.     for(int i = n - 1; i >= 0; i--){
  30.         for(int len = k; len <= mx[i]; len++){
  31.             dp[i] |= dp[i + len];
  32.         }
  33.     }
  34.     cout << (dp[0] ? "YES\n" : "NO\n");
  35. }
  36.  
  37. int main() {
  38.     freopen("killua.in", "r", stdin);
  39.     Speed();
  40.     int tc = 1;
  41.     //cin >> tc;
  42.     while (tc--) {
  43.         solve();
  44.     }
  45.     return 0;
  46. }
Add Comment
Please, Sign In to add comment