Advertisement
mehulJ21

Untitled

May 2nd, 2021
159
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.87 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define rep(i,n) for(int i = 0; i < (n); ++i)
  4. #define rrep(i,n) for(int i = 1; i <= (n); ++i)
  5. #define ll long long
  6. #define int ll
  7. const int N = 2e5 + 5;
  8. const int INF = 1e9+1;
  9. const int mod = 1e9+7;
  10.  
  11.  
  12. ll add(ll x, ll y) {
  13. x += y;
  14. if (x >= mod) return x - mod;
  15. return x;
  16. }
  17.  
  18. ll sub(ll x, ll y) {
  19. x -= y;
  20. if (x < 0) return x + mod;
  21. return x;
  22. }
  23.  
  24. ll mult(ll x, ll y) {
  25. return (x * y) % mod;
  26. }
  27.  
  28. int power(int x,int n,int M){
  29. if(n < 0)
  30. return 0;
  31. int result=1;
  32. while(n>0)
  33. {
  34. if(n % 2 ==1)
  35. result=(result * x)%M;
  36. x=(x*x)%M;
  37. n=n/2;
  38. }
  39. return result;
  40. }
  41.  
  42. void counting_sort(vector<int> &p , vector<int> &c){
  43. int n = p.size();
  44.  
  45. vector<int> cnt(n);
  46. for(auto x : c){
  47. cnt[x]++;
  48. }
  49. vector<int> pnew(n);
  50. vector<int> pos(n);
  51. pos[0] = 0;
  52. for(int i = 1 ; i < n ; i++){
  53. pos[i] = pos[i-1] + cnt[i-1];
  54. }
  55. for(auto x : p){
  56. int i = c[x];
  57. pnew[pos[i]] = x;
  58. pos[i]++;
  59. }
  60. p = pnew;
  61.  
  62. }
  63.  
  64. vector<int> longest_common_prefix(vector<int>& p , vector<int>& c , string& s){
  65. int n = s.size();
  66. vector<int> lc(n);
  67. int k = 0;
  68. for(int i = 0 ; i < n-1 ; i++){
  69. int pi = c[i];
  70. int j = p[pi-1];
  71. while(s[i+k] == s[j+k])
  72. k++;
  73. lc[pi] = k;
  74. k = max(k-1,0LL);
  75. }
  76. return lc;
  77. }
  78.  
  79. pair<vector<int>,vector<int>> suffix_array(string& s){
  80. s+='#';
  81. int n = s.size();
  82. vector<int> p(n),c(n);
  83. {
  84. vector<pair<char,int>> a(n);
  85. for(int i = 0 ; i < n ; i++)
  86. a[i] = {s[i],i};
  87. sort(a.begin(),a.end());
  88.  
  89. for(int i = 0 ; i < n ; i++) p[i] = a[i].second;
  90. c[p[0]] = 0;
  91. for(int i = 1 ; i < n ; i++){
  92. if(a[i].first == a[i-1].first){
  93. c[p[i]] = c[p[i-1]];
  94. }
  95. else{
  96. c[p[i]] = c[p[i-1]] + 1;
  97. }
  98. }
  99. }
  100. int k = 0;
  101. while((1 << k) < n){
  102. for(int i = 0 ; i < n ; i++){
  103. p[i] = (p[i] - (1 << k)+n)%n;
  104. }
  105. counting_sort(p,c);
  106. vector<int> cnew(n);
  107. cnew[p[0]] = 0;
  108. for(int i = 1 ; i < n ; i++){
  109. pair<int,int> prev = {c[p[i-1]],c[(p[i-1]+(1 << k))%n]};
  110. pair<int,int> now = {c[p[i]],c[(p[i]+(1 << k))%n]};
  111. if(now == prev){
  112. cnew[p[i]] = cnew[p[i-1]];
  113. }
  114. else{
  115. cnew[p[i]] = cnew[p[i-1]] + 1;
  116. }
  117. }
  118. c = cnew;
  119. k++;
  120. }
  121. return {p,c};
  122. }
  123.  
  124. int cases = 0;
  125. struct Solver{
  126. void solve(){
  127. string str;
  128. cin >> str;
  129. int K;
  130. cin >> K;
  131. int n = str.size();
  132. if(K*2 > (n)*(n+1)){
  133. cout<<"No such line.\n";
  134. return;
  135. }
  136. pair<vector<int>,vector<int>> l = suffix_array(str);
  137. vector<int> p = l.first , c = l.second;
  138. vector<int> lcp = longest_common_prefix(p,c,str);
  139. // n++;
  140. lcp[0] = -1;
  141. // for(auto x : p)
  142. // cout<<x<<" ";
  143. // for(auto x : lcp)
  144. // cout<<x<<" ";
  145. // cout<<n<<" ";
  146. vector<int> pred(n+1,0);
  147. for(int i = 1 ; i <= n ; i++){
  148. for(int k = pred[i]+1 ; k <= n-p[i] ; k++){
  149. for(int j = i ; j <= n ; j++){
  150. if(j > i && lcp[j] < k)
  151. break;
  152. pred[j] = k;
  153. K--;
  154. if(K==0){
  155. cout<<str.substr(p[i],k);
  156. return;
  157. }
  158. }
  159. }
  160. }
  161. }
  162. };
  163.  
  164. int32_t main(){
  165. ios_base::sync_with_stdio(NULL);
  166. cin.tie(NULL);
  167. cout.tie(NULL);
  168. cout<<fixed<<setprecision(10);
  169. int ts = 1;
  170. rrep(ti,ts) {
  171. cases++;
  172. Solver solver;
  173. solver.solve();
  174. }
  175. return 0;
  176.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement