fork(21) download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/detail/standard_policies.hpp>
  4. using ll = int64_t;
  5. using ld = long double;
  6. using ull = uint64_t;
  7. using namespace std;
  8. using namespace __gnu_pbds;
  9. typedef vector <int> vi;
  10. typedef pair <int, int> ii;
  11.  
  12. const int INF = (int)1e9;
  13.  
  14. #define maxn 100010
  15.  
  16. #define MAX_N 100010 // second approach: O(n log n)
  17.  
  18. char T[MAX_N]; // the input string, up to 100K characters
  19. int n; // the length of input string
  20. int RA[MAX_N], tempRA[MAX_N]; // rank array and temporary rank array
  21. int SA[MAX_N], tempSA[MAX_N]; // suffix array and temporary suffix array
  22. int c[MAX_N]; // for counting/radix sort
  23.  
  24. void countingSort(int k) { // O(n)
  25.     int i, sum, maxi = max(300, n); // up to 255 ASCII chars or length of n
  26.     memset(c, 0, sizeof c); // clear frequency table
  27.     for (i = 0; i < n; i++) // count the frequency of each integer rank
  28.         c[i + k < n ? RA[i + k] : 0]++;
  29.     for (i = sum = 0; i < maxi; i++) {
  30.         int t = c[i]; c[i] = sum; sum += t; }
  31.     for (i = 0; i < n; i++) // shuffle the suffix array if necessary
  32.         tempSA[c[SA[i]+k < n ? RA[SA[i]+k] : 0]++] = SA[i];
  33.     for (i = 0; i < n; i++) // update the suffix array SA
  34.         SA[i] = tempSA[i];
  35. }
  36.  
  37. void constructSA() { // this version can go up to 100000 characters
  38.     int i, k, r;
  39.     for (i = 0; i < n; i++) RA[i] = T[i]; // initial rankings
  40.     for (i = 0; i < n; i++) SA[i] = i; // initial SA: {0, 1, 2, ..., n-1}
  41.     for (k = 1; k < n; k <<= 1) { // repeat sorting process log n times
  42.         countingSort(k); // actually radix sort: sort based on the second item
  43.         countingSort(0); // then (stable) sort based on the first item
  44.         tempRA[SA[0]] = r = 0; // re-ranking; start from rank r = 0
  45.         for (i = 1; i < n; i++) // compare adjacent suffixes
  46.             tempRA[SA[i]] = // if same pair => same rank r; otherwise, increase r
  47.                     (RA[SA[i]] == RA[SA[i-1]] && RA[SA[i]+k] == RA[SA[i-1]+k]) ? r : ++r;
  48.         for (i = 0; i < n; i++) // update the rank array RA
  49.             RA[i] = tempRA[i];
  50.         if (RA[SA[n-1]] == n-1) break; // nice optimization trick
  51.     }
  52. }
  53.  
  54. int main() {
  55. #ifdef BZ
  56.     freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);
  57. #endif
  58.     ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout.setf(ios::fixed); cout.precision(6);
  59.  
  60.  
  61.     n = 1e5;
  62.     for(int i = 0; i < n; i++) {
  63.         T[i] = (char)('a' + rand() % 26);
  64.     }
  65.     T[n] = '\0';
  66.  
  67.     //cout << T << "\n";
  68.  
  69.     n = (int)strlen(T); // input T as per normal, without the ‘$’
  70.     T[n++] = '$'; // add terminating character
  71.     T[n] = '\0';
  72.     constructSA();
  73.  
  74.     set <char> vowels, cons;
  75.  
  76.     vowels.insert('a');
  77.     vowels.insert('e');
  78.     vowels.insert('i');
  79.     vowels.insert('o');
  80.     vowels.insert('u');
  81.  
  82.     int last_cons = 0;
  83.  
  84.     for(int i = 0; i < n - 1; i++) {
  85.         if(!vowels.count(T[i])) {
  86.             last_cons = i;
  87.         }
  88.     }
  89.  
  90.     //cout << last_cons << "\n";
  91.  
  92.     string fi, se;
  93.  
  94.     for(int i = 1; i < n; i++) {
  95.         if(SA[i] < last_cons and vowels.count(T[SA[i]])) {
  96.             int end = 0;
  97.             for(int j = SA[i]; j < n - 1; j++) {
  98.                 fi += T[j];
  99.                 if(!vowels.count(T[j])) {
  100.                     break;
  101.                 }
  102.             }
  103.             break;
  104.         }
  105.     }
  106.  
  107.     for(int i = n - 1; i >= 1; i--) {
  108.         if(SA[i] < last_cons and vowels.count(T[SA[i]])) {
  109.             int end = 0;
  110.             for(int j = SA[i]; j <= last_cons; j++) {
  111.                 se += T[j];
  112.             }
  113.             break;
  114.         }
  115.     }
  116.  
  117.     cout << fi << "\n" << se.substr(0, 20) << "\n";
  118. }
Success #stdin #stdout 0.01s 5216KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
aaaec
uzzzclfqsdjwdjbelcza
https://ideone.com/p3GrTT
language:
C++14 (gcc 8.3)
created:
6 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!