“strcmp()” Anyone?
strcmp() is a library function in C/C++ which compares two strings. It takes two strings as input parameter and decides which one is lexicographically larger or smaller: If the first string is greater then it returns a positive value, if the second string is greater it returns a negative value and if two strings are equal it returns a zero. The code 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 |
The number of comparisons required to
compare two strings in strcmp() function is never returned by the
function. 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 the two strings until two different characters
are found or both strings come to an end. 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
comparisons are 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 7 Comparisons |
Returns positive 7 Comparisons |
|||||||||||
Input
The input file contains maximum 10
sets of inputs. The description of each set is given below:
Each set starts with an integer N
(0
Input is terminated by a line containing a single zero. Input file
size is around 23 MB.
Output
For each set of
input produce one line of output. This line contains the serial of
output followed by an integer T. This T denotes the total number of
comparisons that are required in the strcmp() function if all the
strings are compared with one another exactly once. So for N
strings the function strcmp() will be called exactly uva11732 - “strcmp()” Anyone?" title="ACM: uva11732 - “strcmp()” Anyone?" height="43" width="67"> times. You have to
calculate total number of comparisons inside the strcmp() function
in those uva11732 - “strcmp()” Anyone?" title="ACM: uva11732 - “strcmp()” Anyone?" height="43" width="67"> calls. You can assume
that the value of T will fit safely in a 64-bit signed integer.
Please note that the most straightforward solution (Worst Case
Complexity O(N2 *1000)) will time out for this
problem.
Sample Input
2
a
b
4
cat
hat
mat
sir
0
Output for Sample Input
Case 1: 1
Case 2: 6
分析：两个字符串比较次数其实是相同字符数*2+（存在不同字符？1：0）；
然后建字典树，dfs一下即可；
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
#define mod 1000000007
#define inf 0x3f3f3f3f
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, ls[rt]
#define Rson mid+1, R, rs[rt]
#define sys system("pause")
#define freopen freopen("in.txt","r",stdin)
const int maxn=4e6+;
using namespace std;
ll gcd(ll p,ll q){return q==?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=;while(q){if(q&)f=f*p;p=p*p;q>>=;}return f;}
inline ll read()
{
ll x=;int f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,m,k,t,cas,h[maxn],tot;
char str[];
ll ans,num[maxn];
struct node
{
int to,nxt,a;
}e[maxn];
void add(int x,int p)
{
tot++;
e[tot].to=tot;
e[tot].nxt=h[x];
e[tot].a=p;
h[x]=tot;
}
void insert(char *p)
{
int now=,len=strlen(p);
num[now]++;
for(int i=;i<=len;i++)
{
int x=(p[i]>=''&&p[i]<='')?p[i]-'':(p[i]>='A'&&p[i]<='Z'?p[i]-'A'+:(p[i]=='\0'?:p[i]-'a'+));
bool flag=false;
int j;
for(j=h[now];j;j=e[j].nxt)
{
int a=e[j].a;
if(a==x)
{
flag=true;
break;
}
}
if(flag)now=e[j].to;
else add(now,x),now=tot;
num[now]++;
}
}
void dfs(int p)
{
ll tmp=;
for(int i=h[p];i;i=e[i].nxt)
{
int to=e[i].to;
ans+=num[to]*(num[to]-);
if(!tmp)tmp=num[to];
else ans+=tmp*num[to],tmp+=num[to];
dfs(to);
}
}
int main()
{
int i,j;
//freopen;
while(~scanf("%d",&n)&&n)
{
ans=;
tot=;
memset(h,,sizeof(h));
memset(num,,sizeof(num));
rep(i,,n)
{
scanf("%s",str);
insert(str);
}
dfs();
printf("Case %d: %lld\n",++cas,ans);
}
//system("Pause");
return ;
}