fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define sd(x) scanf("%d", &(x))
  6.  
  7. const int N = 1000006;
  8. const int base = 541;
  9. const int mod = 1e9 + 7;
  10.  
  11. map<int, int> hashes[30][30];
  12. int pw[N];
  13. int freq[26];
  14. set<int> lengths;
  15. int x[N];
  16. int pwr[N];
  17.  
  18. int main(){
  19. 	int t, n, l;
  20. 	cin.tie(0);
  21. 	ios_base::sync_with_stdio(0);
  22. 	cin >> t;
  23. 	pwr[0] = 1;
  24. 	for(int i = 1; i < N; i++) pwr[i] = (pwr[i - 1] * 1ll * base) % mod;
  25. 	for(int T =1; T <= t; T++){
  26. 		cerr << "T = " << T << endl;
  27. 		cin >> l;
  28. 		for(int i = 0; i < 30; i++)
  29. 			for(int j = 0; j < 30; j++) hashes[i][j].clear();
  30. 		lengths.clear();
  31. 		for(int i = 1; i <= l; i++){
  32. 			string s;
  33. 			cin >> s;
  34. 			memset(freq, 0, sizeof freq);
  35. 			for(int j = 0; j < s.length(); j++) freq[s[j] - 'a']++;
  36. 			int h = 0;
  37. 			for(int j = 25; j >= 0; j--) h = (h * 1ll * base + freq[j] + 1) % mod;
  38. 			hashes[s[0] - 'a'][s[s.length() - 1] - 'a'][h]++;
  39. 			lengths.insert(s.length());
  40. 		}
  41. 		char s1, s2;
  42. 		int a, b, c, d;
  43. 		cin >> s1 >> s2 >> n >> a >> b >> c >> d;
  44. 		x[0] = s1;
  45. 		x[1] = s2;
  46. 		for(int i = 2; i < n; i++) x[i] = (a * 1ll * x[i - 1] + b * 1ll * x[i - 2] + c) % d;
  47. 		x[0] -= 'a';
  48. 		x[1] -= 'a';
  49. 		for(int i = 2; i < n; i++){
  50. 			x[i] %= 26;
  51. 		}
  52.  
  53. 		int ans = 0;
  54. 		int cntr = 0;
  55. 		for(int len : lengths){
  56. 			memset(freq, 0, sizeof freq);
  57. 			for(int i = 0; i < len; i++) freq[x[i]]++;
  58. 			int h = 0;
  59. 			for(int j = 25; j >= 0; j--) h = (h * 1ll * base + freq[j] + 1) % mod;
  60. 			for(int i = 0; i + len - 1 < n; i++){
  61. 				if(hashes[x[i]][x[i + len - 1]].find(h) != hashes[x[i]][x[i + len - 1]].end()){
  62. 					ans += hashes[x[i]][x[i + len - 1]][h];
  63. 					hashes[x[i]][x[i + len - 1]][h] = 0;
  64. 				}
  65. 				h += pwr[x[i + len]];
  66. 				h -= pwr[x[i]];
  67. 				if(h >= mod) h -= mod;
  68. 				if(h < 0) h += mod;
  69. 			}
  70. 		}
  71. 		cout << "Case #" << T << ": " << ans << endl;
  72. 	}
  73. }
Runtime error #stdin #stdout #stderr 0.01s 6864KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
T = 1
https://ideone.com/zmTwjr
language:
C++14 (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!