首页 > 代码库 > UVA 11732 strcmp() Anyone? (Trie)
UVA 11732 strcmp() Anyone? (Trie)
strcmp() Anyone?
题意:输入n个字符串,两两调用一次strcmp(),问字符比较的总次数是多少?
考虑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]; }
思路:首先单词两两比较一定有n*(n-1)/2。然后建立Trie树,每插入一个单词,如果当前字母在树上还没有节点存在,则不比较,如果已经存在,则比较次数为该结点当前的访问次数*2。要注意如果两个单词相同,还需要最后比较一次。这里用普通的Trie树是不行的,必须将Trie树用前向星的方式存储。
代码:
/* ID: wuqi9395@126.com PROG: LANG: C++ */ #include<map> #include<set> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<vector> #include<string> #include<fstream> #include<cstring> #include<ctype.h> #include<iostream> #include<algorithm> #define INF (1<<30) #define PI acos(-1.0) #define mem(a, b) memset(a, b, sizeof(a)) #define rep(i, n) for (int i = 0; i < n; i++) #define debug puts("===============") typedef long long ll; using namespace std; const int maxnode = 4001000; struct Trie { int head[maxnode], next[maxnode], tot[maxnode], ed[maxnode]; char ch[maxnode]; int sz; ll sum; void init() { sz = 1; sum = 0; head[0] = next[0] = tot[0] = 0; } void insert(char *s) { int u = 0, v, n = strlen(s); for (int i = 0; i < n; i++) { bool ok = 0; for (v = head[u]; v; v = next[v]) { if (ch[v] == s[i]) { ok = 1; break; } } if (!ok) { v = sz++; tot[v] = ed[v] = 0; ch[v] = s[i]; next[v] = head[u]; head[u] = v; head[v] = 0; } u = v; sum += tot[v] * 2; tot[v]++; } sum += ed[u]; ed[u]++; } }T; int main () { int cnt = 1, n; char str[1100]; while(~scanf("%d", &n), n) { T.init(); rep(i, n) { scanf("%s", str); T.insert(str); } printf("Case %d: %lld\n", cnt++, T.sum + (ll)n * (n - 1) / 2); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。