fork download
copy 
  1. /**
  2. 	Template by Akikaze (秋風) - formerly proptit_4t41.
  3. 	Code written by a random fan of momocashew and Chiho.
  4. **/
  5.  
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8.  
  9. /** -----BASIC MACROES----- **/
  10. #define endl '\n'
  11. #define i64 long long
  12. #define ld long double
  13. #define pub push_back
  14. #define mp make_pair
  15. #define fi first
  16. #define se second
  17. const long long MOD = 1000000007LL, INF = 1e9, LINF = 1e18;
  18. const long double PI = 3.141592653589793116, EPS = 1e-9, GOLD = ((1+sqrt(5))/2);
  19. typedef vector<i64> vi;
  20. typedef vector<ld> vd;
  21. typedef vector<string> vs;
  22. typedef vector<bool> vb;
  23. typedef pair<i64, i64> pii;
  24. typedef pair<i64, pii> pip;
  25. typedef pair<pii, i64> ppi;
  26.  
  27. /** -----BIT CONTROLS----- **/
  28. template<class T> int getbit(T s, int i) { return (s >> 1) & 1; }
  29. template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
  30. template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
  31. template<class T> int cntbit(T s) { return __builtin_popcount(s); }
  32.  
  33. /** -----IDEAS/ALGORITHMS-----
  34. 	Z Algorithm
  35.     -------------------------- **/
  36.  
  37. /** -----CUSTOM TYPEDEFS/DEFINES----- **/
  38.  
  39.  
  40. /** -----GLOBAL VARIABLES----- **/
  41. string A, B, BZA;
  42. i64 len; vi Z;
  43.  
  44. /** -----EXTENSIVE FUNCTIONS----- **/
  45.  
  46.  
  47. /** -----COMPULSORY FUNCTIONS----- **/
  48. void VarInput() {
  49. 	getline(cin, A); getline(cin, B);
  50.  
  51. 	// Initialize array to perform Z-Algorithm: string B, then a unique character (which is guaranteed to NOT appear on both strings), then string A.
  52. 	BZA = B; BZA += "$"; BZA += A;
  53. 	len = BZA.size();
  54.  
  55. 	// Pre-processing Z array
  56. 	Z.resize(len, 0); Z[0] = -1; // Z[0] initialization just for laughs
  57. 	i64 x = 0, y = 0; // Keeping track for an interval [x,y] such as the subsequence within these indices is a subsequence of BZA, and y is maximal.
  58. 	for (i64 i=1; i<len; i++) {
  59. 		// The rule is, if i + Z[i-x] < y, it is certain that Z[i] = Z[i-x].
  60. 		// If not, temporarily set Z[i] = y-i+1
  61. 		Z[i] = max(0LL, min(Z[i-x], y-i+1));
  62.  
  63. 		// then iterate until either the new subsequence does not match any longer or y reaches the end of BZA. Remember to update [x,y] interval.
  64. 		while (i+Z[i] < len && BZA[Z[i]] == BZA[i+Z[i]]) {
  65. 			x = i; y = i + Z[i]; Z[i]++;
  66. 		}
  67. 	}
  68. }
  69.  
  70. void ProSolve() {
  71. 	// Iterating through the Z-array
  72. 	for (i64 i=B.size()+1; i<len; i++) {
  73. 		if (Z[i] == B.size()) { // Subsequence from index i matches the prefix with the size |B| of BZA, which is the original string B itself
  74. 			cout << (i-(i64)B.size()) << " ";
  75. 		}
  76. 	}
  77. 	cout << "";
  78. }
  79.  
  80. /** -----MAIN FUNCTION----- **/
  81. int main() {
  82. 	//freopen("FILE.INP", "r", stdin);
  83. 	//freopen("FILE.OUT", "w", stdout);
  84. 	ios_base::sync_with_stdio(0); cin.tie(NULL);
  85. 	VarInput(); ProSolve(); return 0;
  86. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
aaaaa
aa
stdout
copy 
1 2 3 4
https://ideone.com/Z8bSz3
Z Algorithm.
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
secret

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!