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