Programming/algorithms/strings/trie/code3.cpp at master · hereismari/Programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/*
  12526 - Cellphone Typing
  https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3971
*/

#include <bits/stdc++.h>

using namespace std;

#define MAX 1000005

struct trie_node {
  bool is_leaf;
  int num_words;
  int next[26];
  trie_node() {
    this->is_leaf = false;
    for(int i = 0; i < 26; i++) this->next[i] = -1;
    this->num_words = 0;
  }
};


int aux;
trie_node trie[MAX];

void build_trie(string s, int i, int cur=0) {

  if(i < s.size()) {

    int c = s[i] - 'a';

    if(trie[cur].next[c] == -1) {
      trie[cur].next[c] = ++aux;
    }

    int nxt = trie[cur].next[c];
    trie[nxt].num_words++;
    trie[nxt].is_leaf = (trie[nxt].is_leaf || (i == s.size()-1));

    build_trie(s, i+1, nxt);
  }
}

float res;
void dfs(int c, int cur, int r=1) {

  // printf("%c\n", 'a' + c);

  int cnt = 0;
  for(int i = 0; i < 26; i++) {
    if(trie[cur].next[i] != -1) cnt++;
  }

  for(int i = 0; i < 26; i++) {
    if(trie[cur].next[i] != -1) {
      int nxt = trie[cur].next[i];
      if(cnt == 1 && !trie[cur].is_leaf) {
        dfs(i, nxt, r);
      } else {
        dfs(i, nxt, r + 1);
      }
    }
  }

  if(trie[cur].is_leaf) {
    // printf("%d\n", r);
    res += r;
  }
}

int main() {

  int n;
  while(scanf("%d", &n) != EOF) {

    aux = 1;
    res = 0.0;
    for(int i = 0; i < MAX; i++) trie[i] = trie_node();

    string s;
    for(int i = 0; i < n; i++) {
      cin >> s;
      build_trie(s, 0);
    }

    for(int i = 0; i < 26; i++) {
      if(trie[0].next[i] != -1) {
        dfs(i, trie[0].next[i]);
      }
    }
    printf("%.2lf\n", res / n);
  }

  return 0;
}