欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

UVA 11732 strcmp() Anyone? strcmp()函数(Trie)

程序员文章站 2022-04-17 21:36:30
...

题意:就是给你n个单词,让他们两两比较,要求他们运用strcmp时,进行比较的次数。

分析:Trie树的一道水题,计个数就行了。

代码(LRJ):

#include<bits/stdc++.h>
using namespace std;

const int maxnode = 4000 * 1000 + 10;
const int sigma_size = 26;

// 字母表为全体小写字母的Trie
struct Trie {
  int head[maxnode]; // head[i]为第i个结点的左儿子编号
  int next[maxnode]; // next[i]为第i个结点的右兄弟编号
  char ch[maxnode];  // ch[i]为第i个结点上的字符
  int tot[maxnode];  // tot[i]为第i个结点为根的子树包含的叶结点总数
  int sz; // 结点总数
  long long ans; // 答案
  void clear() { sz = 1; tot[0] = head[0] = next[0] = 0; } // 初始时只有一个根结点

  // 插入字符串s(包括最后的'\0'),沿途更新tot
  void insert(const char *s) {
    int u = 0, v, n = strlen(s);
    tot[0]++;
    for(int i = 0; i <= n; i++) {
      // 找字符a[i]
      bool found = false;
      for(v = head[u]; v != 0; v = next[v])
        if(ch[v] == s[i]) { // 找到了
          found = true;
          break;
        }
      if(!found) {
        v = sz++; // 新建结点
        tot[v] = 0;
        ch[v] = s[i];
        next[v] = head[u];
        head[u] = v; // 插入到链表的首部
        head[v] = 0;
      }
      u = v;
      tot[u]++;
    }
  }

  // 统计LCP=u的所有单词两两的比较次数之和
  void dfs(int depth, int u) {
    if(head[u] == 0) // 叶结点
      ans += tot[u] * (tot[u] - 1) * depth;
    else {
      int sum = 0;
      for(int v = head[u]; v != 0; v = next[v])
        sum += tot[v] * (tot[u] - tot[v]); // 子树v中选一个串,其他子树中再选一个
      ans += sum / 2 * (2 * depth + 1); // 除以2是每种选法统计了两次
      for(int v = head[u]; v != 0; v = next[v])
        dfs(depth+1, v);
    }
  }

  // 统计
  long long count() {
    ans = 0;
    dfs(0, 0);
    return ans;
  }
};

#include<cstdio>
const int maxl = 1000 + 10;   // 每个单词最大长度

int n;
char word[maxl];
Trie trie;

int main() {
  int kase = 1;
  while(scanf("%d", &n) == 1 && n) {
    trie.clear();
    for(int i = 0; i < n; i++) {
      scanf("%s", word);
      trie.insert(word);
    }
    printf("Case %d: %lld\n", kase++, trie.count());
  }
  return 0;
}

 

相关标签: trie

上一篇: idea模板

下一篇: 初识IDEA