UVA - 11732 strcmp() Anyone?

本文主要是介绍UVA - 11732 strcmp() Anyone?，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：题目给出了标准strcmp()函数的代码，给你n个单词（n  <= 4000, len <= 1000， 大小写字母+数字），问你这些单词两两调用strcmp()函数一共比较了多少次

思路：字符串S1，S2比较分两种情况：S1和S2有相同的前缀S，那么ans = len(S)*2+1;

S1和S2完全相同的话：ans = （len(S)+1） * 2，等于算上了‘\0’

然后按照Trie的构造方法：采用了左儿子右兄弟的方法，但是看到网上的都是提交错误，就先存着

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 4000000;struct Trie{int left[MAXN];int right[MAXN];int val[MAXN];char ch[MAXN];int cnt;long long ans;void init(){ch[0] = 0;left[0] = right[0] = val[0] = 0;cnt = 1,ans = 0;}void insert(char *s){int len = strlen(s),u = 0,j;for (int i = 0; i <= len; i++){for (j = left[u]; j; j = right[j])if (ch[j] == s[i])break;if (j == 0){j = cnt++;ch[j] = s[i],right[j] = left[u];left[j] = 0,left[u] = j,val[j] = 0;}ans += (val[u]-val[j])*(i<<1|1);if (i == len){ans += val[j] * ((i+1) << 1);val[j]++;}val[u]++,u = j;}}
}tree;
char str[2000];int main(){int n,cas = 1;while (scanf("%d",&n) != EOF && n){tree.init();for (int i = 0; i < n; i++){scanf("%s",str);tree.insert(str);}printf("Case %d: %lld\n",cas++,tree.ans);}return 0;
}

这篇关于UVA - 11732 strcmp() Anyone?的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---