fork download
copy 
  1. /*
  2.  * Bidhan Roy
  3.  * University of Dhaka
  4.  */
  5.  
  6. using namespace std;
  7.  
  8. #include <algorithm>
  9. #include <bitset>
  10. #include <cmath>
  11. #include <cstdio>
  12. #include <cstdlib>
  13. #include <cstring>
  14. #include <iostream>
  15. #include <list>
  16. #include <ctime>
  17. #include <map>
  18. #include <queue>
  19. #include <set>
  20. #include <sstream>
  21. #include <stack>
  22. #include <string>
  23. #include <vector>
  24.  
  25. #define rep(i,n) for(__typeof(n) i=0; i<(n); i++)
  26. #define foreach(i,n) for(__typeof((n).begin())i =(n).begin();i!=(n).end();i++)
  27. #define inf (1<<30)
  28. #define eps 1e-9
  29. #define pb push_back
  30. #define ins insert
  31. #define mp make_pair
  32. #define sz(x) ((int)x.size())
  33. #define clr clear()
  34. #define all(x) x.begin(),x.end()
  35. #define xx first
  36. #define yy second
  37. #define sqr(x) ((x)*(x))
  38. #define mem(x,val) memset((x),(val),sizeof(x));
  39. #define read(x) freopen(x,"r",stdin);
  40. #define rite(x) freopen(x,"w",stdout);
  41. #define chk(a,k) ((bool)(a&(1<<(k))))
  42. #define off(a,k) (a&(~(1<<(k))))
  43. #define on(a,k) (a|(1<<(k)))
  44.  
  45. typedef long long i64;
  46. typedef unsigned long long ui64;
  47. typedef string st;
  48. typedef vector<int> vi;
  49. typedef vector<st> vs;
  50. typedef map<int,int> mii;
  51. typedef map<st,int> msi;
  52. typedef map<int,st> mis;
  53. typedef set<int> si;
  54. typedef set<st> ss;
  55. typedef pair<int,int> pii;
  56. typedef vector<pii> vpii;
  57.  
  58. const int MAXN = 100000+100000+5;
  59. const int MAXL = 30;
  60. int n ,stp,mv,suffix[MAXN],tmp[MAXN];
  61. int sum[MAXN],cnt[MAXN],rank[MAXL][MAXN];
  62. char str[MAXN];
  63. int LCP(int u,int v){
  64. 	int ret=0,i;
  65. 	for(i = stp; i >= 0; i--){
  66. 		if(rank[i][u]==rank[i][v]){
  67. 			ret += 1<<i;
  68. 			u += 1<<i;
  69. 			v += 1<<i;
  70. 		}
  71. 	}
  72. 	return ret;
  73. }
  74. bool equal(int u,int v){
  75. 	if(!stp)return str[u]==str[v];
  76. 	if(rank[stp-1][u]!=rank[stp-1][v]) return false;
  77. 	int a = u + mv < n ? rank[stp-1][u+mv] : -1;
  78. 	int b = v + mv < n ? rank[stp-1][v+mv] : -1;
  79. 	return a == b ;
  80. }
  81. void upd(){
  82. 	int i;
  83. 	for(i = 0;i < n; i ++) sum[ i ] = 0;
  84.  
  85. 	int rnk = 0;
  86. 	for(i = 0;i < n;i++){
  87. 		suffix[ i ] = tmp[ i ];
  88. 		if( i&&!equal(suffix[i],suffix[i-1])){
  89. 			rank[stp][suffix[i]]=++rnk;
  90. 			sum[rnk+1]=sum[rnk];
  91. 		}
  92. 		else rank[stp][suffix[i]]=rnk;
  93. 		sum[rnk+1]++;
  94. 	}
  95. }
  96. void srt(){
  97. 	int i;
  98. 	for(i = 0; i < n; i ++ ) cnt[ i ] = 0;
  99. 	memset(tmp,-1,sizeof tmp);
  100. 	for(i = 0 ; i < mv; i ++){
  101. 		int idx = rank[ stp - 1 ][ n-i-1 ];
  102. 		int x = sum[ idx ];
  103. 		tmp[ x + cnt[ idx ] ] = n-i-1;
  104. 		cnt[ idx ]++;
  105. 	}
  106. 	for(i = 0;i < n; i ++ ){
  107. 		int idx = suffix[ i ] - mv;
  108. 		if(idx<0)continue;
  109. 		idx = rank[stp-1][idx];
  110. 		int x = sum[ idx ];
  111. 		tmp[ x + cnt[ idx ] ] = suffix[ i ] - mv;
  112. 		cnt[idx]++;
  113. 	}
  114. 	upd();
  115. 	return;
  116. }
  117. bool cmp(const int &a,const int &b){
  118. 	if(str[a]!=str[b]) return str[a]<str[b];
  119. 	return false;
  120. }
  121. char temp[MAXN/2];
  122. int main(){
  123.     int test;
  124.     scanf("%d",&test);
  125.     while(test--){
  126.         scanf("%d",&n);
  127.         scanf ("%s",str);
  128.         strcpy(temp,str);
  129.         strcat(str,temp);
  130.         n*=2;
  131.         int i;
  132.         for(i = 0;i < n;i++) tmp[ i ] = i ;
  133.         sort(tmp,tmp+n,cmp);
  134.         stp = 0;
  135.         upd();
  136.         ++stp;
  137.         for( mv = 1; mv < n;  mv <<= 1){
  138.             srt();
  139.             stp++;
  140.         }
  141.         stp--;
  142.         for(i = 0;i<=stp; i++)	rank[ i ][ n ] = -1;
  143.         int hlf=n/2,ans=suffix[0];
  144.         rep(i,n){
  145.             if(suffix[i]<hlf){
  146.                 int LL=LCP(suffix[i],ans);
  147.                 if(LL==n-ans) ans=min(ans,suffix[i]);
  148.             }
  149.         }
  150.         printf("%d\n",ans);
  151.     }
  152. 	return 0;
  153. }
Compilation error #stdin compilation error #stdout 0s 10144KB
comments (?)
stdin
copy 
1
3 bab
compilation info 
prog.cpp: In function ‘int LCP(int, int)’:
prog.cpp:66:6: error: reference to ‘rank’ is ambiguous
   if(rank[i][u]==rank[i][v]){
      ^
prog.cpp:61:25: note: candidates are: int rank [30][200005]
 int sum[MAXN],cnt[MAXN],rank[MAXL][MAXN];
                         ^
In file included from /usr/include/c++/4.8/bits/move.h:57:0,
                 from /usr/include/c++/4.8/bits/stl_pair.h:59,
                 from /usr/include/c++/4.8/utility:70,
                 from /usr/include/c++/4.8/algorithm:60,
                 from prog.cpp:8:
/usr/include/c++/4.8/type_traits:1243:12: note:                 template<class> struct std::rank
     struct rank
            ^
prog.cpp:66:18: error: reference to ‘rank’ is ambiguous
   if(rank[i][u]==rank[i][v]){
                  ^
prog.cpp:61:25: note: candidates are: int rank [30][200005]
 int sum[MAXN],cnt[MAXN],rank[MAXL][MAXN];
                         ^
In file included from /usr/include/c++/4.8/bits/move.h:57:0,
                 from /usr/include/c++/4.8/bits/stl_pair.h:59,
                 from /usr/include/c++/4.8/utility:70,
                 from /usr/include/c++/4.8/algorithm:60,
                 from prog.cpp:8:
/usr/include/c++/4.8/type_traits:1243:12: note:                 template<class> struct std::rank
     struct rank
            ^
prog.cpp: In function ‘bool equal(int, int)’:
prog.cpp:76:5: error: reference to ‘rank’ is ambiguous
  if(rank[stp-1][u]!=rank[stp-1][v]) return false;
     ^
prog.cpp:61:25: note: candidates are: int rank [30][200005]
 int sum[MAXN],cnt[MAXN],rank[MAXL][MAXN];
                         ^
In file included from /usr/include/c++/4.8/bits/move.h:57:0,
                 from /usr/include/c++/4.8/bits/stl_pair.h:59,
                 from /usr/include/c++/4.8/utility:70,
                 from /usr/include/c++/4.8/algorithm:60,
                 from prog.cpp:8:
/usr/include/c++/4.8/type_traits:1243:12: note:                 template<class> struct std::rank
     struct rank
            ^
prog.cpp:76:21: error: reference to ‘rank’ is ambiguous
  if(rank[stp-1][u]!=rank[stp-1][v]) return false;
                     ^
prog.cpp:61:25: note: candidates are: int rank [30][200005]
 int sum[MAXN],cnt[MAXN],rank[MAXL][MAXN];
                         ^
In file included from /usr/include/c++/4.8/bits/move.h:57:0,
                 from /usr/include/c++/4.8/bits/stl_pair.h:59,
                 from /usr/include/c++/4.8/utility:70,
                 from /usr/include/c++/4.8/algorithm:60,
                 from prog.cpp:8:
/usr/include/c++/4.8/type_traits:1243:12: note:                 template<class> struct std::rank
     struct rank
            ^
prog.cpp:77:23: error: reference to ‘rank’ is ambiguous
  int a = u + mv < n ? rank[stp-1][u+mv] : -1;
                       ^
prog.cpp:61:25: note: candidates are: int rank [30][200005]
 int sum[MAXN],cnt[MAXN],rank[MAXL][MAXN];
                         ^
In file included from /usr/include/c++/4.8/bits/move.h:57:0,
                 from /usr/include/c++/4.8/bits/stl_pair.h:59,
                 from /usr/include/c++/4.8/utility:70,
                 from /usr/include/c++/4.8/algorithm:60,
                 from prog.cpp:8:
/usr/include/c++/4.8/type_traits:1243:12: note:                 template<class> struct std::rank
     struct rank
            ^
prog.cpp:78:23: error: reference to ‘rank’ is ambiguous
  int b = v + mv < n ? rank[stp-1][v+mv] : -1;
                       ^
prog.cpp:61:25: note: candidates are: int rank [30][200005]
 int sum[MAXN],cnt[MAXN],rank[MAXL][MAXN];
                         ^
In file included from /usr/include/c++/4.8/bits/move.h:57:0,
                 from /usr/include/c++/4.8/bits/stl_pair.h:59,
                 from /usr/include/c++/4.8/utility:70,
                 from /usr/include/c++/4.8/algorithm:60,
                 from prog.cpp:8:
/usr/include/c++/4.8/type_traits:1243:12: note:                 template<class> struct std::rank
     struct rank
            ^
prog.cpp: In function ‘void upd()’:
prog.cpp:89:4: error: reference to ‘rank’ is ambiguous
    rank[stp][suffix[i]]=++rnk;
    ^
prog.cpp:61:25: note: candidates are: int rank [30][200005]
 int sum[MAXN],cnt[MAXN],rank[MAXL][MAXN];
                         ^
In file included from /usr/include/c++/4.8/bits/move.h:57:0,
                 from /usr/include/c++/4.8/bits/stl_pair.h:59,
                 from /usr/include/c++/4.8/utility:70,
                 from /usr/include/c++/4.8/algorithm:60,
                 from prog.cpp:8:
/usr/include/c++/4.8/type_traits:1243:12: note:                 template<class> struct std::rank
     struct rank
            ^
prog.cpp:92:8: error: reference to ‘rank’ is ambiguous
   else rank[stp][suffix[i]]=rnk;
        ^
prog.cpp:61:25: note: candidates are: int rank [30][200005]
 int sum[MAXN],cnt[MAXN],rank[MAXL][MAXN];
                         ^
In file included from /usr/include/c++/4.8/bits/move.h:57:0,
                 from /usr/include/c++/4.8/bits/stl_pair.h:59,
                 from /usr/include/c++/4.8/utility:70,
                 from /usr/include/c++/4.8/algorithm:60,
                 from prog.cpp:8:
/usr/include/c++/4.8/type_traits:1243:12: note:                 template<class> struct std::rank
     struct rank
            ^
prog.cpp: In function ‘void srt()’:
prog.cpp:101:13: error: reference to ‘rank’ is ambiguous
   int idx = rank[ stp - 1 ][ n-i-1 ];
             ^
prog.cpp:61:25: note: candidates are: int rank [30][200005]
 int sum[MAXN],cnt[MAXN],rank[MAXL][MAXN];
                         ^
In file included from /usr/include/c++/4.8/bits/move.h:57:0,
                 from /usr/include/c++/4.8/bits/stl_pair.h:59,
                 from /usr/include/c++/4.8/utility:70,
                 from /usr/include/c++/4.8/algorithm:60,
                 from prog.cpp:8:
/usr/include/c++/4.8/type_traits:1243:12: note:                 template<class> struct std::rank
     struct rank
            ^
prog.cpp:109:9: error: reference to ‘rank’ is ambiguous
   idx = rank[stp-1][idx];
         ^
prog.cpp:61:25: note: candidates are: int rank [30][200005]
 int sum[MAXN],cnt[MAXN],rank[MAXL][MAXN];
                         ^
In file included from /usr/include/c++/4.8/bits/move.h:57:0,
                 from /usr/include/c++/4.8/bits/stl_pair.h:59,
                 from /usr/include/c++/4.8/utility:70,
                 from /usr/include/c++/4.8/algorithm:60,
                 from prog.cpp:8:
/usr/include/c++/4.8/type_traits:1243:12: note:                 template<class> struct std::rank
     struct rank
            ^
prog.cpp: In function ‘int main()’:
prog.cpp:142:32: error: reference to ‘rank’ is ambiguous
         for(i = 0;i<=stp; i++) rank[ i ][ n ] = -1;
                                ^
prog.cpp:61:25: note: candidates are: int rank [30][200005]
 int sum[MAXN],cnt[MAXN],rank[MAXL][MAXN];
                         ^
In file included from /usr/include/c++/4.8/bits/move.h:57:0,
                 from /usr/include/c++/4.8/bits/stl_pair.h:59,
                 from /usr/include/c++/4.8/utility:70,
                 from /usr/include/c++/4.8/algorithm:60,
                 from prog.cpp:8:
/usr/include/c++/4.8/type_traits:1243:12: note:                 template<class> struct std::rank
     struct rank
            ^
stdout
copy 
Standard output is empty
https://ideone.com/fgYur6
language:
C++14 (gcc 8.3)
created:
9 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!