[UVA] 11732 - strcmp() Anyone?
J | “strcmp()” Anyone? Input: Standard Input Output: Standard Output |
strcmp() is a library function inC/C++ which compares two strings. It takes two strings as input parameter anddecides which one is lexicographically larger or smaller: If the first stringis greater then it returns a positive value, if the second string is greater itreturns a negative value and if two strings are equal it returns a zero. Thecode that is used to compare two strings in C/C++ library is shown below:
| int strcmp(char *s, char *t) |
| Figure: The standard strcmp() code provided for this problem. |
The number of comparisonsrequired to compare two strings in strcmp() function is never returned by thefunction. But for this problem you will have to do just that at a larger scale.strcmp() function continues to compare characters in the same position of thetwo strings until two different characters are found or both strings come to anend. Of course it assumes that last character of a string is a null (‘\0’) character.For example the table below shows what happens when “than” and “that”; “therE”and “the” are compared using strcmp() function. To understand how 7 comparisonsare needed in both cases please consult the code block given above.
| t | h | a | N | \0 |
| t | h | e | r | E | \0 |
|
| = | = | = | ≠ |
| = | = | = | ≠ |
|
| ||
| t | h | a | T | \0 | t | h | e | \0 |
|
| ||
| Returns negative value 7 Comparisons | Returns positive value 7 Comparisons | |||||||||||
Input
The input file contains maximum 10sets of inputs. The description of each set is given below:
Each set starts with an integer N(0<N<4001) which denotes the total number of strings. Each of the next Nlines contains one string. Strings contain only alphanumerals (‘0’… ‘9’, ‘A’…‘Z’, ‘a’… ‘z’) have a maximum length of 1000, and a minimum length of 1.
Input is terminated by a line containing a single zero.Input file size is around 23 MB.
Output
For each setof input produce one line of output. This line contains the serial of outputfollowed by an integer T. This T denotes the total number of comparisons thatare required in the strcmp() function if all the strings are compared with oneanother exactly once. So for N strings the function strcmp() will be called exactly
times. You have tocalculate total number of comparisons inside the strcmp() function in those calls. You can assumethat the value of T will fit safely in a 64-bit signed integer. Please notethat the most straightforward solution (Worst Case Complexity O(N2*1000)) will time out for this problem.
Sample Input Output for SampleInput
| 2 a b 4 cat hat mat sir 0 | Case 1: 1 Case 2: 6
|
作法 : 基數排序
#include<stdio.h>
#include<string.h>
char str[4000][1002];
struct {
int st, ed;
}Range1[8000], Range2[8000], *RA, *RB, *RT;
long long solve(int n) {
RA = Range1, RB = Range2;
int i, j, k, Rt = 1, RBt, tRBt;
long long Ans = 0;
int S0[8000], S1[8000], *A, *B, *T, asci[128], tmp, tn;
RA[0].st = 0, RA[0].ed = n-1;
A = S0, B = S1;
for(i = 0; i < n; i++) S0[i] = i;
for(i = 0; ; i++) {
if(Rt == 0) break;
RBt = 0;
for(k = 0; k < Rt; k++) {
tRBt = RBt;
if(RA[k].st >= RA[k].ed || (i > 0 && str[A[RA[k].st]][i-1] == '\0')) continue;
memset(asci, 0, sizeof(asci));
for(j = RA[k].st; j <= RA[k].ed; j++)
asci[str[A[j]][i]]++;
for(j = 1; j < 128; j++) asci[j] += asci[j-1];
for(j = RA[k].ed; j >= RA[k].st; j--)
B[--asci[str[A[j]][i]]+RA[k].st] = A[j];
int start = RA[k].st;
/*printf("<");
for(j = RA[k].st; j <= RA[k].ed; j++) {
printf("%c", str[B[j]][i]);
}
printf(">");*/
for(j = RA[k].st+1; j <= RA[k].ed; j++) {
if(str[B[j]][i] == str[B[j-1]][i]) continue;
else {
RB[RBt].st = start, RB[RBt].ed = j-1;
start = j;
RBt++;
}
}
RB[RBt].st = start, RB[RBt].ed = j-1;
RBt++;
for(j = tRBt, tmp = 0, tn; j < RBt; j++) {
tn = RB[j].ed - RB[j].st + 1;
Ans += tn*(tn-1);
Ans += tn*tmp;
tmp += tn;
}
}
/* puts("");*/
T = A, A = B, B = T;
RT = RA, RA = RB, RB = RT;
Rt = RBt;
}
return Ans;
}
int main() {
int N, C = 0, i, k = 0;
while(scanf("%d", &N) == 1 && N) {
getchar();
for(i = 0; i < N; i++) scanf("%s", str[i]);
printf("Case %d: %lld\n", ++C, solve(N));
}
return 0;
}
/*
7
aaaa
aaaa
aaaa
aaaa
aaaa
aaaa
aaaa
*/