beads.cpp

/*
Algoritmo tomado del libro Competitive Programing 3
*/

#include <iostream> 
#include <algorithm>
#include <stdio.h>
#include <string.h>
#define MAX_N 100010 // second approach: O(n log n) 
std::string T; // the input string, up to 100K characters 
int n; // the length of input string 
int RA[MAX_N], tempRA[MAX_N]; // rank array and temporary rank array 
int SA[MAX_N], tempSA[MAX_N]; // suffix array and temporary suffix array 
int c[MAX_N]; 

void countingSort(int k) { // O(n) 
    int i, sum, maxi = std::max(300, n); // up to 255 ASCII chars or length of n 
    memset(c, 0, sizeof c); // clear frequency table 
    for (i = 0; i < n; i++) // count the frequency of each integer rank 
        c[i + k < n ?RA[i + k] : 0]++; 
    for (i = sum = 0; i < maxi; i++) { 
        int t = c[i]; c[i] = sum; sum += t; } 
    for (i = 0; i < n; i++) // shuffle the suffix array if necessary 
        tempSA[c[SA[i]+k < n ? RA[SA[i]+k] : 0]++] = SA[i]; 
    for (i = 0; i < n; i++) // update the suffix array SA 
        SA[i] = tempSA[i]; 
}


void constructSA() { // this version can go up to 100000 characters 
    int i, k, r; 
    for (i = 0; i < n; i++) RA[i] = T[i]; // initial rankings 
    for (i = 0; i < n; i++) SA[i] = i; // initial SA: {0, 1, 2, ..., n-1} 
    for (k = 1; k < n; k <<= 1) { // repeat sorting process log n times 
        countingSort(k); // actually radix sort: sort based on the second item 
        countingSort(0); // then (stable) sort based on the first item 
        tempRA[SA[0]] = r = 0; // re-ranking; start from rank r = 0 
        for (i = 1; i < n; i++){ // compare adjacent suffixes 
            // if same pair => same rank r; otherwise, increase r
            tempRA[SA[i]] =  (RA[SA[i]] == RA[SA[i-1]] && RA[SA[i]+k] == RA[SA[i-1]+k]) ? r : ++r;
        }
        for (i = 0; i < n; i++) // update the rank array RA 
            RA[i] = tempRA[i]; 
        if (RA[SA[n-1]] == n-1) break; // nice optimization trick 
    }
}

int main()
{
    char aux[MAX_N];
    int cases;
    scanf("%d", &cases);
    for(int i = 0 ; i < cases ; i++)
    {
        scanf("%s", aux);
        T = aux;
        T += aux;
        n = T.size();
        T[n++] = '~';
        constructSA();
 
        for (int j = 0; j < n; j++)
        {
            if(SA[j] < n/2)
            {
                printf("%d\n", (SA[j] + 1));
                break;
            }
        }
    }
    return 0;
}