suffixarray.cpp

Bài viết đang được chỉnh sửa

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

int n;

long H[92309];

char a[92309];

int b[92309];

long pow2309[92309];

void hash(int n){

    for (int i=1; i<=n; i++) H[i] = H[i-1] * 2309 + a[i];

    pow2309[0]=1;

    for (int i=1; i<=n; i++) pow2309[i] = pow2309[i-1] * 2309;

}

long hash(int pos, int len){

    return H[pos+len-1] - H[pos-1] * pow2309[len];

}

int compare(int p, int q, int len){

    if (len==1) return a[p]-a[q];

    if (hash(p, len) == hash(q, len)) return 0;

    int i = compare(p, q, len/2);

    if (i==0) return compare(p+len/2, q+len/2, len-len/2);

    else return i;

}

int compare(const void * a, const void * b){

    return compare(*(int*)a, *(int*)b, n);

}

main(){

    int i, T;

    scanf("%d", &T);

while (T--){

    scanf("%s", a+1);

    n = strlen(a+1);

    strncat(a+1, a+1, n);

    for (i=1; i<=n; i++) b[i]=i;

    hash(n*2);

    qsort(b+1, n, sizeof(int), compare);

    //for (i=1; i<=n; i++) printf(i==n?"%d\n":"%d ", b[i]);

    printf("%d\n", b[1]);

}

}

Nhận xét