strcmp()函数

【题目描述】

strcmp()是c/c++的一个库函数，它的作用是比较两个字符串的字典序大小。在本题中，考虑strcmp()的如下实现。

int strcmp(char *s,char *t)

{

 int i;

 for(i=0;s[i]==t[i];i++)

   if(s[i]=='\0')

     return 0;

 return s[i]-t[i];

}

如上所述，比较操作一直进行到两个字符串的对应位置处的字符不相同为止（假定字符串总是以'\0'结尾）。比如，strcmp("than","that")和strcmp("there","the")各需要7次比较（注意s[i]==t[i]和s[i]=='\0'各有一次比较），如下图所示。

输入n个字符串，两两调用一次strcmp()(即一共调用n(n-1)/2次)，问字符比较的总次数是多少？

【输入格式】

输入文件包含不超过10组测试数据，每组测试数据的第一行为一个整数N(0<N<4001),即字符串总数，接下来N行每行包含一个不超过1000个由'0'~'9'、'a~z'和'A~Z'组成的非空字符串。输入结束标志为N=0。输入文件大小约为23M。

【输出格式】

对于每组测试数据，输出一行内容，先输出测试数据编号，再输出字符比较的总次数T（详细输出格式见样例）。输入保证T在64位带符号整数范围内。

【样例输入】

2
a
b
4
cat
hat
mat
sir
0

【样例输出】

Case 1: 1
Case 2: 6

【来源】

《算法竞赛入门经典-训练指南》