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

From UMCPC Wiki
Jump to navigation Jump to search
m (Q2 (unsolved))
m
 
Line 3: Line 3:
 
== Example ==
 
== Example ==
 
Wordlist:
 
Wordlist:
<syntaxhighlight>
+
<syntaxhighlight lang="text">
 
word
 
word
 
in
 
in

Latest revision as of 16:29, 16 August 2018

Trie (prefix tree)

Example

Wordlist:

word
in
inn
algo
algae
stop

Tree:

UYX34zc.png

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$ .