fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector<int> kmp(string a, string b) {
  6. 	int k[b.length()];
  7. 	k[0] = 0;
  8. 	int i = 1, j = 0;
  9. 	while (i < b.size()) {
  10. 		if (b[i] == b[j])
  11. 			k[i] = j + 1, i++, j++;
  12. 		else if (j == 0)
  13. 			k[i] = 0, i++;
  14. 		else
  15. 			j = k[j - 1];
  16. 	}
  17.  
  18. 	vector<int> v;
  19. 	i = j = 0;
  20. 	while (i < a.size()) {
  21. 		if (j == b.size())
  22. 			v.push_back(i - j), j = k[j - 1];
  23. 		else if (a[i] == b[j])
  24. 			i++, j++;
  25. 		else if (j == 0)
  26. 			i++;
  27. 		else
  28. 			j = k[j - 1];
  29. 	}
  30. 	if (j == b.size())
  31. 		v.push_back(i - j);
  32. 	return v;
  33. }
  34. //main code
  35. int main()
  36. {
  37. 	int T;
  38. 	cin >> T;
  39. 	while (T--) {
  40. 		string s, t;
  41. 		cin >> t >> s;
  42. 		string p = "";
  43. 		int n = s.size(), m = t.size();
  44. 		vector<string> parts;
  45. 		for (int i = 0; i < m; i++) {
  46. 			if (t[i] == '*') {
  47. 				if (p != "")
  48. 					parts.push_back(p), p = "";
  49. 			}
  50. 			else
  51. 				p += t[i];
  52. 		}
  53. 		if (p != "")
  54. 			parts.push_back(p);
  55.  
  56. 		if (parts.size() == 0) {
  57. 			for (int i = 0; i < n; i++)
  58. 				cout << i + 1 << " ";
  59. 		}
  60. 		else {
  61. 			vector<int> dp;
  62. 			for (int i = 0; i < n; i++)
  63. 				dp.push_back(i - 1);
  64.  
  65. 			for (auto part : parts) {
  66. 				vector<int> temp = kmp(s, part);
  67. 				for (int i = 0, j = 0; i < n && dp[i] != -2; i++) {
  68. 					if (j == temp.size())
  69. 						dp[i] = -2;
  70. 					else if (dp[i] >= temp[j])
  71. 						j++, i--;
  72. 					else
  73. 						dp[i] = temp[j] + part.size() - 1;
  74. 				}
  75. 			}
  76.  
  77. 			for (int i = 0; i < dp.size(); i++)
  78. 				cout << dp[i] + 1 << " ";
  79. 		}
  80. 		cout << "\n";
  81. 	}
  82. 	return 0;
  83. }
Success #stdin #stdout 0.01s 5392KB
comments (?)
stdin
copy 
2
*a*
abacaba
*a*b*
abacaba
stdout
copy 
1 3 3 5 5 7 7 
2 6 6 6 6 -1 -1
https://ideone.com/UlXurv
language:
C++14 (gcc 8.3)
created:
1 year 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!