fork download
copy 
  1. /* 
  2.    Copyright 2013 Jakub "Cubix651" Cisło
  3.    Dictionary of base factors (DBF)
  4.    Complexity: O(n log n + q log n)
  5.    
  6.    This algorithm is impractical, a better way is coding DBF
  7.    using STL in complexity O(n log^2 n) - it's easier
  8.    and the difference in speed is invisible.
  9. */
  10. #include <cstdio>
  11. #include <cstring>
  12. #include <vector>
  13. #define PB push_back
  14. using namespace std;
  15.  
  16. const int MAXLEN = 500007, LOG = 30, SIGMA = 1000007;
  17. int dbf[MAXLEN][LOG];
  18.  
  19. vector<vector<int> > countingSort(vector<vector<int> > tab, int size, int idx)
  20. {
  21. 	vector<vector<int> > res;
  22. 	res.resize(size);
  23. 	for(int i = 0; i < size; ++i)
  24. 		res[i] = vector<int>();
  25.  
  26. 	int cnt[SIGMA], tmp;
  27. 	for(int i = 0; i < SIGMA; ++i)
  28. 		cnt[i] = 0;
  29. 	for(int i = 0; i < size; ++i)
  30. 		++cnt[tab[i][idx]];
  31. 	for(int i = 1; i < SIGMA; ++i)
  32. 		cnt[i] += cnt[i-1];
  33. 	for(int i = SIGMA-1; i > 0; --i)
  34. 		cnt[i] = cnt[i-1];
  35. 	cnt[0] = 0;
  36. 	for(int i = 0; i < size; ++i)
  37. 		res[cnt[tab[i][idx]]++] = tab[i];
  38. 	return res;
  39. }
  40.  
  41. vector<vector<int> > radixSort(vector<vector<int> > tab, int size, int k)
  42. {
  43. 	for(int i = k-1; i >= 0; --i)
  44. 		tab = countingSort(tab, size, i);
  45. 	return tab;
  46. }
  47.  
  48. void DBF(char *s, int size)
  49. {
  50. 	for(int i = 0; i < size; ++i)
  51. 		dbf[i][0] = s[i]-'a';
  52.  
  53. 	int len = 1, idx = 1;
  54. 	vector<vector<int> > vec;
  55.  
  56. 	vec.resize(size);
  57.  
  58.  
  59. 	while(2*len <= size)
  60. 	{
  61. 		for(int i = 0; i + 2*len <= size; ++i)
  62. 		{
  63. 			vec[i] = vector<int>();
  64. 			vec[i].PB(dbf[i][idx-1]);
  65. 			vec[i].PB(dbf[i+len][idx-1]);
  66. 			vec[i].PB(i);
  67. 		}
  68.  
  69. 		vec = radixSort(vec, size - 2*len + 1, 2);
  70.  
  71. 		dbf[vec[0][2]][idx] = 0;
  72. 		for(int i = 1; i + 2*len <= size; ++i)
  73. 			dbf[vec[i][2]][idx] = dbf[vec[i-1][2]][idx] + ((vec[i][0]==vec[i-1][0] && vec[i][1]==vec[i-1][1])?0:1);
  74.  
  75. 		++idx;
  76. 		len <<= 1;
  77. 	}
  78. }
  79.  
  80. bool equal(int a, int b, int s)
  81. {
  82. 	if(a == b || s == 0)
  83. 		return true;
  84.  
  85. 	//this part can be preprocessed and complexity will O(n log n + q)
  86. 	int pow = 1, idx = -1;
  87. 	while(pow <= s)
  88. 	{
  89. 		pow <<= 1;
  90. 		++idx;
  91. 	}
  92. 	pow >>= 1;
  93. 	return ((dbf[a][idx] == dbf[b][idx]) && (dbf[a+s-pow][idx] == dbf[b+s-pow][idx]));
  94. }
  95.  
  96. int main()
  97. {
  98. 	char *str = "abbaabbabababbaaaba";
  99. 	DBF(str, strlen(str));
  100. 	printf("%s\n", equal(3, 15, 3) ? "tak" : "nie");
  101. 	printf("%s\n", equal(3, 15, 4) ? "tak" : "nie");
  102. 	return 0;
  103. }
Success #stdin #stdout 0.05s 65416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
tak
nie
https://ideone.com/Wz9HSB
language:
C++ (gcc 8.3)
created:
11 years 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!