AhmedAshraff

Untitled

Jul 17th, 2024
26
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 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