fork download
copy 
  1. // عَجَبًا لأَمْرِ المُؤْمِنِ، إنَّ أمْرَهُ كُلَّهُ خَيْرٌ
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. using ll = long long;
  5. using ld = long double;
  6. const char el = '\n';
  7.  
  8. const int N = 2, M = 998244353;
  9.  
  10. void ama_aan() {
  11. 	int n, m, k;
  12. 	cin >> n >> m >> k;
  13. 	string a, b, s;
  14. 	cin >> a >> b;
  15. 	s = b + "#" + a;
  16. 	int p[s.size()]{};
  17. 	for (int i = 1, j = 0; i < s.size(); i++) {
  18. 		while (j && s[j] != s[i]) j = p[j - 1];
  19. 		p[i] = j += s[j] == s[i];
  20. 	}
  21. 	int lst = b.size() + 1;
  22. 	for (int i = b.size() + 1; i < s.size(); i++) {
  23. 		if (p[i] == b.size()) {
  24. 			int j = i - b.size() + 1;
  25. 			if (j - lst <= k) {
  26. 				lst = i;
  27. 			}
  28. 		}
  29. 	}
  30. 	cout << (lst == s.size() - 1 ? "YES" : "NO");
  31. }
  32.  
  33. int main() {
  34. 	cin.tie(0)->sync_with_stdio(0);
  35. 	cout << fixed << setprecision(10);
  36. #if Mosaab
  37. 	freopen("input.txt", "r", stdin);
  38. 	freopen("output.txt", "w", stdout);
  39. #endif
  40. 	int t = 1;
  41. 	cin >> t;
  42. 	while (t--) ama_aan(), cout << el;
  43. }
  44.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
3
5 2 2
abcab
ab
6 2 2
abcabc
ab
4 3 1
hgaa
gaa
stdout
copy 
YES
NO
YES
https://ideone.com/tHIOxL
language:
C++ (gcc 8.3)
created:
1 hour ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!