Topic 9: String: Hash, KMP, AC Automata

CS 311 - Competitive Programming II (Fall 2023)

Zhongtang Luo (Instructor)

Code Presentation

Problem… (Subsequences in Substrings)

NAIPC 2019

Not all problems need a technique…

Sample: s=aaaaa, t=aaa

String Search

• Find some string t in a very long string s
• Naive complexity O(|t||s|)
• Goal: make it O(|t|+|s|)

String Search: Rolling Hash

• Treat string as a number / two numbers

String Search: Rolling Hash

• Theory
• Insecure: small modular / non-prime modular / fixed modular & base
• Secure: fixed prime modular + randomized base (|Z|+1 – p-1)
• Secure: randomized prime modular (N – 2N) + fixed base
• See also: Hash Killer
• See also: https://codeforces.com/blog/entry/60442
• Practice
• …

Problem… (Palindromes)

There are very famous algorithms that deal with palindromes (Manacher, palindrome tree, etc.)

But for this problem, try to solve it with hash + BSTA.

String Match: Trie?

Problem… (Remember the Word)

String Search: Automata

• Automata for t=’abcd’
• Automata for t=’aab’
• Automata for t=’ababc’

String Search: KMP

• Optimization on mismatch

String Search: AC Automata

Problem… (Anthem of Berland)

Hint: let dp[i][j] be the case that we are at i-th position in the string and at the j-th position in KMP.

Problem… (DNA repair)