Strings

tags: conteudo ps2020 strings trie KMP

Trie

• Estrutura de dados
• Prefix Tree
• Cada aresta representa um símbolo do alfabeto
• Cada nó representa uma palavra, que corresponde a todas as arestas no caminho da raiz até o nó

Lista de palavras:

t
to
te
tea
ted
ten
A
i
in
inn

struct node {
  int cnt;
  node *children[alphabet_size]; 
};

/*  NÃO USAMOS ISSO
node *add(node* u, char c) {
  c -= 'a';
  if(node->children[c] == NULL) node->children = (node*) malloc(sizeof(node));
  return node->children[c];
}

node root;
void addw(char s[N]) {
  node *u = &root;
  
  for(int i = 0; s[i] != '\0'; i++) {
    u = add(u, s[i]);
  }
  
}
*/

Supondo que eu tenho o seguinte conjunto de palavras:

{to, te, tea, ted, ten, inn}

Nós: t, to (1), te(1), tea(1), ted(1), ten(1), i, in, inn(1)

Procurar palavra int

verifica se existe aresta 'i' saindo do nó ""
vai pra o nó i
verifica se existe a aresta 'n' saind do nó "i"
vai pra o nó "in"
verificar se existe a aresta 't' saindo do nó "in"
return false (não existe a palavra na minha trie)

//alfabeto: ['a' - 'z']
const int sz = 26;
const int N = 1e5;

int trie[N][sz];
int trien;
int triecnt[N];

int add(int u, char c) {
  //if(c >= '0' and c <= '9') c -= '0';
  //else if(c >= 'a' and c <= 'z') c -= 'a' - 10;
  c -= 'a';
  
  if(trie[u][c]) return trie[u][c];
  return trie[u][c] = ++trien;
}

void addw(char s[N]) {
  int u = 0;
  
  for(int i = 0; s[i]; i++) {
    u = add(int u, char c);
  }
  triecnt[u]++;
}

n = 693

diga um número que quando fizer xor com 693 dá 554

n = 001010110101