fork(3) download
copy 
  1. #pragma region include
  2.  
  3. #define _CRT_SECURE_NO_WARNINGS
  4. #include<stdio.h>
  5. #include<iostream>
  6. #include<sstream>
  7. #include<queue>
  8. #include<math.h>
  9. #include<stdlib.h>
  10. #include<stack>
  11. #include<string.h>
  12. #include<string>
  13. #include<map>
  14. #include<algorithm>
  15. #include<time.h>
  16. #include<set>
  17. #include<vector>
  18. #include<numeric>
  19. #include<iomanip>
  20. #include <bitset>
  21. #include <functional>
  22. using namespace std;
  23.  
  24. #pragma endregion
  25.  
  26. #pragma region define 
  27. #define All(a) a.begin(), a.end()
  28. #define _2d(a,row,col,type) type**a=new type*[row]; for (int i=0;i<row;i++) a[i]=new type[col];
  29. #define rep(i,n) for(int i=0;i<int(n);i++)
  30. #define repd(i,n) for(int i=n-1;i>=0;i--)
  31. #define repi(i,a,n) for(int i=int(a);i<int(n);i++)
  32. #define clr(a, n) memset(a, n, sizeof(a));
  33. #define scn(a,n) rep(i,n) cin>>a[i];
  34. #define scn2(a,row,col) rep(i,row) rep(j,col) cin>>a[i][j];
  35. #define prn(a,n) rep(i,n-1) cout<<a[i]<<" "; cout<<a[n-1]<<endl;
  36. #define prn2(a,row,col) rep(i,row){rep(j,col-1) cout<<a[i][j]<<" "; cout<<a[i][col-1]<<endl;}
  37. #define mp make_pair
  38. #define Odd(x) x%2!=0
  39. #define Even(x) x%2==0
  40. #define Pi 3.14159265358979323846
  41. #define INF 2000000000 // 2 billion
  42. #define read freopen("in.in","r",stdin)
  43. #define write freopen("out.out","w",stdout)
  44. #define IOS  ios::sync_with_stdio(false)
  45. #define MOD (1e9 + 7)
  46. #define SQR(x) (x) * (x)
  47. #pragma endregion
  48.  
  49. #pragma region typedef
  50.  
  51. typedef long long ll;
  52. typedef unsigned long ul;
  53. typedef unsigned long long ull;
  54. typedef long double ld;
  55. typedef vector<int> vi;
  56. typedef vector<vi > vivi;
  57. typedef vector<long> vl;
  58. typedef vector<ll> vll;
  59. typedef vector<double> vd;
  60. typedef vector<string> vs;
  61. typedef pair<int, string> is;
  62. typedef pair<int, int> pii;
  63. typedef pair<pair<int,int>, ll> pi;
  64.  
  65.  
  66. #pragma endregion
  67.  
  68. int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
  69. int lcm(int a, int b) { return a * (b / gcd(a, b)); }
  70.  
  71. const int maxn = 10005;
  72. char * s;
  73. int n, gap;
  74. int sa[maxn], pos[maxn], tmp[maxn], lcp[maxn];
  75.  
  76. bool sufcmp(int i, int j)
  77. {
  78. 	if (pos[i] != pos[j])
  79. 		return pos[i] < pos[j];
  80. 	i += gap;
  81. 	j += gap;
  82. 	return (i < n && j < n) ? pos[i] < pos[j] : i > j;
  83. }
  84.  
  85. void buildsa(string s)
  86. {
  87. 	n = s.length();
  88. 	rep(i, n) sa[i] = i, pos[i] = s[i];
  89. 	for (gap = 1;; gap *= 2)
  90. 	{
  91. 		sort(sa, sa + n, sufcmp);
  92. 		rep(i, n - 1) tmp[i + 1] = tmp[i] + sufcmp(sa[i], sa[i + 1]);
  93. 		rep(i, n) pos[sa[i]] = tmp[i];
  94. 		if (tmp[n - 1] == n - 1) break;
  95. 	}
  96. }
  97.  
  98. void buildlcp(string s)
  99. {
  100. 	for (int i = 0, k = 0; i < n; ++i) if (pos[i] != n - 1)
  101. 	{
  102. 		for (int j = sa[pos[i] + 1]; s[i + k] == s[j + k];)
  103. 			++k;
  104. 		lcp[pos[i]] = k;
  105. 		if (k)--k;
  106. 	}
  107. }
  108.  
  109. int main()
  110. {
  111. 	//read;
  112. 	//write;
  113. 	int t, k = 1;
  114. 	cin >> t;
  115. 	string s;
  116. 	while (t--){
  117. 		cin >> s;
  118. 		buildsa(s);
  119. 		buildlcp(s);
  120. 		ll res = 0;
  121. 		int A, B; cin >> A >> B;
  122. 		rep(i, n){
  123. 			if (n - s[i] < A) continue;
  124.  
  125. 			int to_add;
  126. 			int l = n - sa[i];
  127. 			int up, down;
  128. 			up = min(l, B);
  129. 			down = max(A, lcp[i]);
  130. 			to_add = max(0, up - down);
  131. 			res += to_add;
  132.  
  133. 		}
  134. 		cout << "Case " << k++ << ": " << res << endl;
  135. 		clr(tmp, 0);
  136. 		clr(lcp, 0);
  137. 		clr(sa, 0);
  138. 		clr(pos, 0);
  139. 	}
  140. 	return 0;
  141. }
Success #stdin #stdout 0s 3576KB
comments (?)
stdin
copy 
50
fffffffffffffffff
12 13
qqqqqqqqqqqqqqqqqqq
5 6
ffffffffffffffffff
4 4
zzzzzzzzzzzzzzz
1 7
uuuuuuuuuuuuuuuuuuuu
15 16
yyyyyyyyy
7 7
xxxxxxxxxxxxx
11 11
kkkkkkkkkkkkkkkkkkkkkk
14 15
lsqewgjbpmkrbfcwlzwlqhgnc
1 1
foecgrxxxtfjvvvhoyoq
1 1
c
1 1
tnhatvcsatyezqdypzeyubvd
1 1
urhqtajj
8 8
kefmxhhvl
9 9
nrfdqjbm
8 8
zpdtimjentnvfrctqjbmwiznnefzirlhircrdnxqi
1 41
n
1 1
fphwaikxslmhqsgajujsllloykhjwwwd
1 32
fzopllhxyppsxpbtyvelgvlqeuoarsowtdo
1 35
qveqmtimkkfkfkvohgglbvlupaskfgrxevosqweaikkqwhgdomor
1 52
bnydhliqcguywmostpddbvzjbeznusxvhxzoijelralnpziiqnns
1 52
odjsewmwvjdtktduaqlabbrbjztwm
1 29
gcqpuuliqjsvecphyrymrznlcykwwzjcbatywggnpa
1 42
tfbbdsb
1 7
mcgxfgjdeimimobklisaxvkraouf
1 28
xuxdtekdjonwzzmalziezgzmzbavgkqffpjywvdflrdksslervkrdjfcmhxsrpyyhjzfgckrtqemirszocssnzwzgwtanryucxziamcveijmzbnndihsherqalsn
72 101
hqlrsxtnbdzpcafsgnzywfsohfgxjzhspumhshwvlvnpwshehjcfqwuybcvnbehqytxsbuqmrfbpxltgwylmuhmy
69 79
lnseombipxabrfegepaklyyaufmsrwfdlyhzmkkbkkcbqihwyhjlhhneoawgycjjcsloevpoftpxbzwbifpsmcwceuicytoalzoqufgby
70 98
xxdfcuxqxvsdqbiouwpivfarlgulevndsrlwlkmkgfqwiymewdotjokwxghbcvfwostbcfmimegwctbawptfgfddllg
70 79
muffvimjqbpxztsatosmwytzdhmjwsxiocpmkexdhncggujakboibkkgrwpnrmyfrntdttgagihoeqqrthzwrjciirxzgvgx
44 61
etjfbtoryeipzpqvicxskqpjwnpvaryemhlpabhahprggi
9 26
aiwtzfrmwnoqlvcugsukzxrqqawydmmguizvpqkmfyeqtgkcahmbgdrwfpxjdjpz
7 9
hgfvmdzexirziankgsdcytbhwlywfotowykkblravibekoqqhtuhowonjojoeccccondaggxqhbaytqfpmodkeqtsbhwfkyhynnatt
60 75
blaxdhmqvpaziutldprpqaqfnqbiqmnuyprbxdruuuucqnovfhlxhbcxtdhksugqkxrjcldwhzbznruuyfrhgvecbomtkslurcftpjpyisxxjstjxmrgixilnwg
72 74
uhvaanjrltkjrtbkfaxwihvs
4 11
ahgtbnodpdmhpir
2 6
blrdkpotlgpwvpfbiirzmgeantigtjvwxmcjeqfrwuntkuxucovqwarmvzuplpnicptgfyxctmxfguzkkxbjzsvut
45 70
fzojoirugqybcvgksiuefvngpiajampfleqbohxwxvybtgnnojrvfhbwpefpqvwdbmervenuz
30 57
wkjkudibklxzpdrfapkdcruxvjswzptvcchwfpxpb
8 20
bkabzkgbdabymvxnmqiosrmajlrmiiejsensrtvuwytivqxigfyaylchyutgcasxefrvaoqwplgkddslk
32 77
eececedeeddabebbceeadaaddbcbeababbedceabcddda
27 43
abedbebecaddbbdceadbedecddcdeecacbdedcaccabaceddedaedbdbe
18 50
cbbbaecddd
8 8
dbcdbbeedaeedbbdaccbddbebbdbeeecceaecaaacabdbebdbdeebdbee
9 32
acbcbdbaacadcdbadcabcebaceaedacacacaebabacbedcebbbcaaababbeeddbdeedaaebcbd
59 69
ccbdcbdecabaecbdeeeacecdceccadacbbcaecbcdeeeeaeaedaeeeccdeeadbebebbeaeddecdaaeab
16 76
cbdbbeddcecdeabdadbbeabecaeedbedeebaeeddeccdeadedecebddeecdeaeeebbbaaeabdeecaeeadbacaabedbaacacdbdadabadabdcbcdbdadaabbaccd
25 51
daabdacdbcabcbdcedcdbeecceeabdcbdcceaecdeeedceaccecdaddccceadbcdbecdbabcbcabbaddbcebaceabdaeceadbcbceebbbbccdccbbdcbcddecb
31 111
aebacaebdcebb
3 5
acbeaddddcceadccedcbbceebdbdbcdecaacadcdbadddaaaaabdebaabdddcceecebecbcabcdbebbcbaacdacedbebadaecedaacadabbecdbaaec
3 63
stdout
copy 
Case 1: 0
Case 2: 0
Case 3: 0
Case 4: 0
Case 5: 0
Case 6: 0
Case 7: 0
Case 8: 0
Case 9: 0
Case 10: 0
Case 11: 0
Case 12: 0
Case 13: 0
Case 14: 0
Case 15: 0
Case 16: 0
Case 17: 0
Case 18: 0
Case 19: 0
Case 20: 0
Case 21: 0
Case 22: 0
Case 23: 0
Case 24: 0
Case 25: 0
Case 26: 0
Case 27: 0
Case 28: 0
Case 29: 0
Case 30: 0
Case 31: 0
Case 32: 0
Case 33: 0
Case 34: 0
Case 35: 0
Case 36: 0
Case 37: 0
Case 38: 0
Case 39: 0
Case 40: 0
Case 41: 0
Case 42: 0
Case 43: 0
Case 44: 0
Case 45: 0
Case 46: 0
Case 47: 992
Case 48: 0
Case 49: 0
Case 50: 4935
https://ideone.com/gds2gU
language:
C++ (gcc 8.3)
created:
8 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!