# Homework 15 - String

## Läxa:
Lös:
- https://open.kattis.com/problems/stringmatching
- https://open.kattis.com/problems/hashing

Lös en av:
- https://open.kattis.com/problems/radiotransmission
- https://open.kattis.com/problems/powerstrings
- https://open.kattis.com/problems/clockpictures

Lös en av:
- https://open.kattis.com/problems/chasingsubs
- https://open.kattis.com/problems/animal

## Bonus

Kul (och svåra) bonusproblem om hashning, för den som känner för det (ersätter godtyckligt problem från ovan):
- http://codeforces.com/problemset/problem/464/E (möjlig hint: persistenta segmentträd [[1]](http://www.geeksforgeeks.org/persistent-segment-tree-set-1-introduction/))
- http://www.spoj.com/problems/TREEISO/ (möjlig hint: centroider [[1]](https://en.wikipedia.org/wiki/Centered_tree) [[2]](https://threads-iiith.quora.com/Centroid-Decomposition-of-a-Tree))

## Läsning
- https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
- https://en.wikipedia.org/wiki/Rolling_hash
- https://en.wikipedia.org/wiki/Trie
- https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm
- https://en.wikipedia.org/wiki/Suffix_array
- https://github.com/kth-competitive-programming/kactl/tree/master/content/strings
- http://www.csc.kth.se/~jsannemo/slask/main.pdf kapitel 16

### Bonus

- Hur man konstruerar en suffix-array i $\mathcal{O}(n)$: https://zork.net/~st/jottings/sais.html#concepts-in-sa-is