a.b.c.d

0 <= a, b, c, d <= 255

abcd

length = 4
alphabet_size = 256

Áîð, Trie (Äåðåâî, Tree)

const int N = (int)1e5 * 4 + 1;

int root, vn;
int next[N][256], is_end[N];

void init()
{
  root = 0;
  vn = 1;
  memset(next, -1, sizeof(next));
}

// 0 <= s[i] < 256
void add( int n, int *ip )
{
  int v = root;
  for (int i = 0; i < n; i++)
  {
    int &r = next[v][ip[i]];
    if (r == -1)
      r = vn++;
    v = r;
  }
  is_end[v] = 1;
}

bool is( int n, int *ip )
{
  int v = root;
  for (int i = 0; i < n; i++)
  {
    int &r = next[v][ip[i]];
    if (r == -1)
      return 0;
    v = r;
  }
  return is_end[v];
}

// Time (add, is) = O(length)
// Memory = O(summary_length * alphabet_size)