https://vjudge.net/problem/UVA-11732
题意：
给出许多字符串，他们两两按下面的函数比较
输出比较次数
s[i]==t[i] , 和 s[i]==' ' 各算一次比较
法一：
每两个字符串，要么全部匹配，要么中间停止匹配
如果全部匹配，比较次数为 2*len+2（‘ ’两次匹配）
如果中间停止匹配，比较次数为 2*相同前缀长度+1 （1次失败匹配后退出）
所以
1、对于第i个字符串，先加上i-1，即假设全部 中间停止匹配
这样最后再加上全部匹配数
2、匹配一个就+sum*2
#include<cstdio> #include<cstring> #define N 1001 using 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<len;i++) { id=get(i); if(!trie[root][id]) { trie[root][id]=++tot; memset(trie[tot],0,sizeof(trie[tot])); sum[tot]=mark[tot]=0; } root=trie[root][id]; ans+=sum[root]<<1; sum[root]++; } ans+=mark[root]; mark[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 ",++t,ans); } }
法二：
用cnt记录现在还剩下几个是匹配的
那么每次
1、ans+=cnt-sum 匹配失败
2、ans+=sum*2 匹配成功
3、cnt=sum
注意：为了好处理，所以字符串的结束符也算上了
那么这就要循环到len，另外特殊给‘ ’赋一个id
#include<cstdio> #include<cstring> #define N 1001 using 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 ",++t,ans); } }