fork download
copy 
  1. // C++ program for building LCP array for given text
  2. #include <bits/stdc++.h>
  3. #include <vector>
  4. #include <string>
  5. #include <unordered_map>
  6. #include <map>
  7. #include <math.h>
  8. #include <time.h>
  9.  
  10. using namespace std;
  11.  
  12. #define MAX 100000
  13. #define mod 1000000007
  14.  
  15. long cum[MAX];
  16.  
  17.  
  18. // Structure to store information of a suffix
  19. struct suffix
  20. {
  21. 	int index; // To store original index
  22. 	int rank[2]; // To store ranks and next rank pair
  23. };
  24.  
  25. // A comparison function used by sort() to compare two suffixes
  26. // Compares two pairs, returns 1 if first pair is smaller
  27. int cmp(struct suffix a, struct suffix b)
  28. {
  29. 	return (a.rank[0] == b.rank[0])? (a.rank[1] < b.rank[1] ?1: 0):
  30. 		(a.rank[0] < b.rank[0] ?1: 0);
  31. }
  32.  
  33. // This is the main function that takes a string 'txt' of size n as an
  34. // argument, builds and return the suffix array for the given string
  35. vector<int>suffixArr;
  36. void buildSuffixArray(string &txt, int n)
  37. {
  38. 	struct suffix suffixes[n];
  39.  
  40. 	for (int i = 0; i < n; i++)
  41. 	{
  42. 		suffixes[i].index = i;
  43. 		suffixes[i].rank[0] = txt[i] - 'a';
  44. 		suffixes[i].rank[1] = ((i+1) < n)? (txt[i + 1] - 'a'): -1;
  45. 	}
  46.  
  47. 	sort(suffixes, suffixes+n, cmp);
  48.  
  49. 	int ind[n];
  50.  
  51. 	for (int k = 4; k < 2*n; k = k*2)
  52. 	{
  53. 		int rank = 0;
  54. 		int prev_rank = suffixes[0].rank[0];
  55. 		suffixes[0].rank[0] = rank;
  56. 		ind[suffixes[0].index] = 0;
  57.  
  58. 		for (int i = 1; i < n; i++)
  59. 		{
  60. 			if (suffixes[i].rank[0] == prev_rank &&
  61. 					suffixes[i].rank[1] == suffixes[i-1].rank[1])
  62. 			{
  63. 				prev_rank = suffixes[i].rank[0];
  64. 				suffixes[i].rank[0] = rank;
  65. 			}
  66. 			else
  67. 			{
  68. 				prev_rank = suffixes[i].rank[0];
  69. 				suffixes[i].rank[0] = ++rank;
  70. 			}
  71. 			ind[suffixes[i].index] = i;
  72. 		}
  73.  
  74. 		for (int i = 0; i < n; i++)
  75. 		{
  76. 			int nextindex = suffixes[i].index + k/2;
  77. 			suffixes[i].rank[1] = (nextindex < n)?
  78. 								suffixes[ind[nextindex]].rank[0]: -1;
  79. 		}
  80.  
  81. 		sort(suffixes, suffixes+n, cmp);
  82. 	}
  83.  
  84. 	for (int i = 0; i < n; i++)
  85. 		suffixArr.push_back(suffixes[i].index);
  86.  
  87. }
  88.  
  89. /* To construct and return LCP (longest common prefix) */
  90. vector<int> lcp(MAX, 0);
  91. vector<int> invSuff(MAX, 0);
  92.  
  93. void kasai(string &txt, vector<int> &suffixArr)
  94. {
  95. 	int n = suffixArr.size();
  96.  
  97. 	for (int i=0; i < n; i++)
  98. 		invSuff[suffixArr[i]] = i;
  99.  
  100. 	int k = 0;
  101.  
  102. 	for (int i=0; i<n; i++)
  103. 	{
  104. 		if (invSuff[i] == n-1)
  105. 		{
  106. 			k = 0;
  107. 			continue;
  108. 		}
  109.  
  110. 		int j = suffixArr[invSuff[i]+1];
  111.  
  112. 		while (i+k<n && j+k<n && txt[i+k]==txt[j+k])
  113. 			k++;
  114.  
  115. 		lcp[invSuff[i]] = k;
  116.  
  117. 		if (k>0)
  118. 			k--;
  119. 	}
  120.  
  121. }
  122.  
  123. // Utility function to print an array
  124. void printArr(vector<int>&arr, int n)
  125. {
  126. 	for (int i = 0; i < n; i++)
  127. 		cout << arr[i] << " ";
  128. 	cout << endl;
  129. }
  130.  
  131. // pow takes integer inputs and returns long long
  132. // this function proves more accurate than math.pow, and quicker
  133. long long ipow(int base_in, int exp)
  134. {
  135. 	long long result = 1;
  136. 	long long base = (long long) base_in;
  137.  
  138. 	if (exp == 1)
  139. 		return base;
  140.  
  141.     while (exp)
  142.     {
  143.         if (exp & 1)  {
  144.             result *= base;
  145.         	result %= mod;
  146.         }
  147.         exp >>= 1;
  148.         base *= base;
  149.         base %= mod;
  150.     }
  151.     return result;
  152. }
  153.  
  154. // store character frquency for each max length suffix
  155. int dist_map[26];
  156.  
  157. string chars = "abcdefghijklmnopqrstuvwxyz";
  158.  
  159. // finds number of unique characters of substring by indexes
  160. // checks for indexes in vector array pos >= begin and <= end
  161.  
  162. void distinct_substr_chars(string &s, int begin, int end)
  163. {
  164. 	for (int i = begin; i <= end; i++)
  165. 	{
  166. 		int c = s[i] - 'a';
  167. 		dist_map[c]++;
  168. 	}
  169. }
  170.  
  171.  
  172. void dist_map_clear()
  173. {
  174. 	//memset(dist_map,0,26);
  175.  
  176. 	for (int i = 0; i < 26; i++)
  177. 		dist_map[i] = 0;
  178. }
  179.  
  180. int dist_map_size()
  181. {
  182. 	int count = 0;
  183. 	for (int i = 0; i < 26; i++)
  184. 		if (dist_map[i] > 0)
  185. 			count++;
  186. 	return count;
  187.  
  188. }
  189. // Driver program
  190. int main()
  191. {
  192. 	int t;
  193. 	cin >> t;
  194.  
  195. 	struct timespec start, finish;
  196. 	double elapsed, total = 0;
  197.  
  198. 	while (t > 0)
  199. 	{
  200.  
  201. 		string str;
  202. 		cin >> str;
  203. 		int n = str.length();
  204.  
  205. 		//Comment following 2 lines for hackerrank submission
  206. 		clock_gettime(CLOCK_MONOTONIC, &start);
  207.  
  208. 		// build suffix array (vector)
  209. 		buildSuffixArray(str, str.length());
  210.  
  211. 		// build lcp (longest common prefix) array (vector)
  212. 		kasai(str, suffixArr);
  213.  
  214. 		// cum will hold number of unique substrings if that'a what you want (total = cum[n-1])
  215. 		// Comment if not used
  216. 		//cum[0] = n - suffixArr[0];
  217.  
  218. 		long long count = 0;
  219.  
  220. 		// loop through suffix array using lcp to get
  221. 		// unique substring begin and end idexes
  222. 		// then uses them to get substring length and
  223. 		// count of distinct characters to perform function
  224. 		int begin_suffix, suffix_len, suffix_end, begin, end;
  225. 		int distinct_chars = 0, base, exp;
  226. 		long long function_p;
  227.  
  228. 		begin = 1;
  229. 		end = n - suffixArr[0];
  230.  
  231. 		for (int i = end; i >= begin; i--)  {
  232.  
  233. 			begin_suffix = suffixArr[0];
  234. 			suffix_len = i;
  235. 			suffix_end = begin_suffix + suffix_len - 1;
  236.  
  237. 			if (i < end) {
  238.  
  239. 				// Decrement character frequency total count if necessary
  240. 				// and update frquency map
  241. 				int c = str[suffix_end+1] - 'a';
  242. 				if (dist_map[c] == 1)
  243. 					distinct_chars--;
  244. 				dist_map[c]--;
  245. 			}
  246. 			else  // i = max suffix length
  247. 			{
  248. 				// Get character frquency for suffix max length
  249. 				 dist_map_clear();
  250. 				 distinct_substr_chars(str, begin_suffix, suffix_end);
  251. 				 distinct_chars = dist_map_size();
  252. 			}
  253.  
  254. 			base = suffix_len;
  255. 			exp = distinct_chars;
  256. 			function_p = ipow(base, exp);
  257. 			count += function_p;
  258. 			count %= mod;
  259. 		}
  260.  
  261. 		// loop through suffix array using lcp to get
  262. 		// unique substring begin and end idexes
  263. 		// then uses them to get substring length and
  264. 		// count of distinct characters to perform function
  265. 		for(int i = 1;i < n;i++)
  266. 		{
  267. 			//Comment next line if not want total number of unique substrings
  268. 			//cum[i] = cum[i-1] + (n - suffixArr[i] - lcp[i - 1]);
  269.  
  270. 			end = n - suffixArr[i];
  271. 			begin = lcp[i-1] + 1;
  272. 			begin_suffix = suffixArr[i];
  273.  
  274. 			for (int j = end, k = end - begin + 1 ; j >= begin; j--, k--)  {
  275.  
  276. 				suffix_len = lcp[i-1] + k;
  277. 				suffix_end = begin_suffix + suffix_len - 1;
  278.  
  279. 				if (j < end)
  280. 				{
  281. 					// Decrement character frequency total count if necessary
  282. 					// and update frquency map
  283. 					int c = str[suffix_end+1] - 'a';
  284. 					if (dist_map[c] == 1)
  285. 						distinct_chars--;
  286. 					dist_map[c]--;
  287. 				}
  288. 				else  // j = max suffix length
  289. 				{
  290. 					// Get character frquency for suffix max length
  291. 					dist_map_clear();
  292. 					distinct_substr_chars(str, begin_suffix, suffix_end);
  293. 					distinct_chars = dist_map_size();
  294. 				}
  295.  
  296. 				base = suffix_len;
  297. 				exp = distinct_chars;
  298. 				function_p = ipow(base,exp);
  299. 				count += function_p;
  300. 				count %= mod;
  301. 			}
  302. 		}
  303.  
  304. 		//Comment next 2 lines for hackerrank submission
  305. 		//cout << endl << "Total unique substrings = " << cum[n-1] << endl << endl;
  306. 		//cout << endl << "Result = ";
  307.  
  308. 		cout << count  <<  endl;
  309.  
  310. 		suffixArr.clear();
  311. 		lcp.clear();
  312. 		invSuff.clear();
  313.  
  314. 		// Comment next 2 lines if not want total number of unique substrings
  315. 		//for ( int j = 0; j < n; j++)
  316. 			//cum[j] = 0;;
  317.  
  318. 		//Comment following 6 lines for hackerrank submission
  319. 		clock_gettime(CLOCK_MONOTONIC, &finish);
  320.  
  321. 		elapsed = (finish.tv_sec - start.tv_sec);
  322. 		elapsed += (finish.tv_nsec - start.tv_nsec) / 1000000000.0;
  323. 		total += elapsed;
  324. 		//cout << endl << "String \t\tExecution time = " << (int) elapsed /60 << " minutes " << fmod(elapsed,60)<< " seconds" << endl;
  325.  
  326. 		t--;
  327.  
  328. 	}
  329.  
  330. 	//Comment following line for hackerrank submission
  331. 	cout << endl << "Total \t\tExecution time = " << (int) total /60 << " minutes " << fmod(total,60)<< " seconds" << endl;
  332.  
  333.  
  334. 	return 0;
  335. }
  336.  
Success #stdin #stdout 0s 3868KB
comments (?)
stdin
copy 
1 swokbwzbur
stdout
copy 
112609122

Total 		Execution time = 0 minutes 3.0267e-05 seconds
https://ideone.com/9f13QC
language:
C++14 (gcc 8.3)
created:
8 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!