fork(1) 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. 	Hashing Algorithm (Multiple modules)
  35.     -------------------------- **/
  36.  
  37. /** -----CUSTOM TYPEDEFS/DEFINES----- **/
  38.  
  39.  
  40. /** -----GLOBAL VARIABLES----- **/
  41. i64 modArr[] = {(i64)1e9+3, (i64)1e9+7, (i64)1e8+3, (i64)1e8+7, (i64)1e7+7, (i64)1e7+3, (i64)1e6+3, (i64)1e6+7};
  42. string A, B;
  43. vector<vi> hashA;
  44. i64 lenA, lenB;
  45. vi hashKey(8, 0), hashMul(8, 1);
  46. vi workingKey(8, 0);
  47.  
  48. /** -----EXTENSIVE FUNCTIONS----- **/
  49. bool keyMatch() {
  50. 	for (i64 i=0; i<8; i++) {
  51. 		if (hashKey[i] != workingKey[i]) return false;
  52. 	}
  53. 	return true;
  54. }
  55.  
  56. /** -----COMPULSORY FUNCTIONS----- **/
  57. void VarInput() {
  58. 	getline(cin, A); getline(cin, B);
  59. 	lenA = A.size(); lenB = B.size();
  60. 	hashA.resize(8, vi(lenA, 0));
  61.  
  62. 	// Initialize hashMul
  63. 	for (i64 x=0; x<8; x++) {
  64. 		for (i64 i=1; i<lenB; i++) hashMul[x] = (hashMul[x] * 257) % modArr[x];
  65. 	}
  66.  
  67. 	// Calculate hashKey
  68. 	for (i64 x=0; x<8; x++) {
  69. 		for (i64 i=0; i<lenB; i++) hashKey[x] = (hashKey[x] * 257 + int(B[i])) % modArr[x];
  70. 	}
  71.  
  72. 	// Pre-processing hashA array and workingKey
  73. 	for (i64 x=0; x<8; x++) {
  74. 		for (i64 i=0; i<lenA; i++) {
  75. 			hashA[x][i] = int(A[i]);
  76. 			if (i < lenB) workingKey[x] = (workingKey[x] * 257 + hashA[x][i]) % modArr[x];
  77. 		}
  78. 	}
  79. }
  80.  
  81. void ProSolve() {
  82. 	if (lenA < lenB) {
  83. 		cout << ""; return;
  84. 	}
  85.  
  86. 	// Prefix match
  87. 	if (keyMatch()) cout << "1 ";
  88.  
  89. 	// Other subsequences
  90. 	for (i64 i=1; i<=lenA-lenB; i++) {
  91. 		for (i64 x=0; x<8; x++) {
  92. 			workingKey[x] = (workingKey[x] - hashA[x][i-1] * hashMul[x]) % modArr[x];
  93. 			while (workingKey[x] < 0) workingKey[x] += modArr[x];
  94. 			workingKey[x] = (workingKey[x] * 257 + hashA[x][i+lenB-1]) % modArr[x];
  95. 		}
  96. 		if (keyMatch()) cout << (i+1) << " ";
  97. 	}
  98. 	cout << "";
  99. }
  100.  
  101. /** -----MAIN FUNCTION----- **/
  102. int main() {
  103. 	//freopen("FILE.INP", "r", stdin);
  104. 	//freopen("FILE.OUT", "w", stdout);
  105. 	//ios_base::sync_with_stdio(0); cin.tie(NULL);
  106. 	VarInput(); ProSolve(); return 0;
  107. }
Success #stdin #stdout 0s 4560KB
comments (?)
stdin
copy 
aaaa
a
stdout
copy 
1 2 3 4
https://ideone.com/caiC8B
Hashing Algorithm (Multiple modules).
language:
C++ (gcc 8.3)
created:
5 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!