fork download
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <map>
  4.  
  5. using namespace std;
  6.  
  7. const int MAXLEN = 1000; // максимальная суммарная длина всех строк
  8.  
  9. struct vertex {
  10. map <char, int> next;
  11. bool leaf;
  12. };
  13.  
  14. int sz;
  15. vertex tr[MAXLEN];
  16.  
  17. void init_trie () {
  18. sz = 0;
  19. for (int i = 0; i < MAXLEN; ++i) {
  20. tr[i].next.clear ();
  21. tr[i].leaf = false;
  22. }
  23. sz++;
  24. }
  25.  
  26. void add_string (string s) {
  27. int v = 0;
  28. for (int i = 0; i < s.length (); ++i) {
  29. if (!tr[v].next.count (s[i])) {
  30. tr[v].next[s[i]] = sz++;
  31. }
  32. v = tr[v].next[s[i]];
  33. }
  34. tr[v].leaf = true;
  35. }
  36.  
  37. main () {
  38. int n;
  39. cin >> n;
  40. init_trie();
  41. for (int i = 0; i < n; ++i) {
  42. string s;
  43. cin >> s;
  44. add_string (s);
  45. }
  46. int v = 0;
  47. int len = 0;
  48. while (tr[v].next.size () == 1) {
  49. ++len;
  50. v = tr[v].next.begin () -> second;
  51. }
  52. cout << len;
  53. }
  54.  
Success #stdin #stdout 0s 3464KB
stdin
4
abcbcbd
abcbcd
abcbcde
abcdbc
stdout
3