题意：

给出许多字符串，他们两两按下面的函数比较

输出比较次数

s[i]==t[i]  ,  和  s[i]=='\0'   各算一次比较 

 

 

 法一：

每两个字符串，要么全部匹配，要么中间停止匹配

如果全部匹配，比较次数为 2*len+2（‘\0’两次匹配）

如果中间停止匹配，比较次数为 2*相同前缀长度+1 （1次失败匹配后退出）

所以

1、对于第i个字符串，先加上i-1，即假设全部 中间停止匹配

这样最后再加上全部匹配数

2、匹配一个就+sum*2

#include
      
       #include
       
        #define N 1001using namespace std;char s[N];int sum[N*4001],len,trie[N*4001][63],tot;long long ans;int mark[N*4001];int get(int i){    if(s[i]>='0'&&s[i]<='9') return s[i]-'0';    if(s[i]>='a'&&s[i]<='z') return s[i]-'a'+10;    if(s[i]>='A'&&s[i]<='Z') return s[i]-'A'+36;}void insert(int cnt){    int root=0,id;    ans+=cnt;    for(int i=0;i
       
      

 

法二：

用cnt记录现在还剩下几个是匹配的

那么每次

1、ans+=cnt-sum 匹配失败

2、ans+=sum*2  匹配成功

3、cnt=sum 

注意：为了好处理，所以字符串的结束符也算上了

那么这就要循环到len，另外特殊给‘\0’赋一个id

#include
      
       #include
       
        #define N 1001using namespace std;char s[N];int sum[N*4001],len,trie[N*4001][63],tot;long long ans;int get(int i){    if(s[i]>='0'&&s[i]<='9') return s[i]-'0';    if(s[i]>='a'&&s[i]<='z') return s[i]-'a'+10;    if(s[i]>='A'&&s[i]<='Z') return s[i]-'A'+36;    return 62;}void insert(int cnt){    int root=0,id;    for(int i=0;i<=len;i++)    {        id=get(i);        if(!trie[root][id])         {            trie[root][id]=++tot;            memset(trie[tot],0,sizeof(trie[tot]));            sum[tot]=0;        }        root=trie[root][id];        ans+=cnt-sum[root];        ans+=sum[root]<<1;        cnt=sum[root];        sum[root]++;    }}int main(){    int n,t=0;    while(scanf("%d",&n)!=EOF)    {        if(!n) return 0;        memset(trie[0],0,sizeof(trie[0]));        ans=0;tot=0;        for(int i=1;i<=n;i++)        {            scanf("%s",s);            len=strlen(s);            insert(i-1);        }        printf("Case %d: %lld\n",++t,ans);    }}