Läxa vecka 15
===

Välj antingen läxa 1 eller läxa 2:

Läxa 1:
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

Läxa 2:
Gör ett bibliotek i valfritt språk som löser generalliserade strängproblem.
Detta biblioteket kan ni såklart sedan använda för tävlingsprogrammering

Man ska enkelt kunna importera biblioteket för att.
Förslagsvis så skapar ni en kattisfil som tar in indata, och som sedan använder sig av erat bibliotek
- https://kth.kattis.com/problems/stringmatching
- https://kth.kattis.com/problems/stringmultimatching
- https://kth.kattis.com/problems/suffixsorting

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/referens:
- 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

Bonusläsning:

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