# Difference between revisions of "4 May 2017: String Processing"

Jump to navigation
Jump to search

m (→Q2 (unsolved)) (Tag: Visual edit) |
m (Tag: Visual edit) |
||

Line 3: | Line 3: | ||

== Example == | == Example == | ||

Wordlist: | Wordlist: | ||

− | <syntaxhighlight> | + | <syntaxhighlight lang="text"> |

word | word | ||

in | in |

## Latest revision as of 17:29, 16 August 2018

## Contents

# Trie (prefix tree)

## Example

Wordlist:

```
word
in
inn
algo
algae
stop
```

Tree:

For all node, keep:

- Words ending at that node (if repeats aren't allowed, instead store a bool: is this a word or just a prefix node)
- No. of words that include this as a prefix

### Add a word

- $O(\text{length of word})$
- Traverse through the tree, and update the numbers accordingly
- Insert nodes when necessary

## Sample question

### Q1

Given array of integer $A$, and integers queries $Q$. For each query $q$ in $Q$, find the $i$ that gives maximum $q\text{ xor }A_i$.

$0 \leq A_i, Q_j < 2^3\ \forall\ i, j \in R_A, R_Q$

- Construct a prefix tree for all elements in $A$ by its binary digits
- Traverse through the tree to find the max possible $\text{xor}$ value

### Q2 (unsolved)

Given array of integer $A$ of length $n$, find $l$ and $r$ ($0 \leq l \leq r < n$ such that $A_l\text{ xor }A_{l+1}\text{ xor }A_{l+2}\text{ xor ... xor }A_r$ is maximum.

- Define $\text{axor}(a[l..r] = A_l\text{ xor }A_{l+1}\text{ xor }A_{l+2}\text{ xor ... xor }A_r$
- $\text{axor}(a[i..j]) = \text{axor}(a[0..j])\text{ xor axor}(a[0..i])$
- Construct empty Trie $T$ .