Princeton Alogorithm COS226 Week
brute force
image.png
except performance, another problem is backup.
in many applications, we want to avoid backup in text stream.
image.png
brute force alogroithm is not always good enough.
linear-time guarantee, avoid backup in text stream;
KMP
suppose we are searching in text for pattern BAAAAAA
suppose we match 5 chars in pattern, with mismatch on 6th char.
we know previous 6 chars in text are BAAAAB
we donot need to back up text pointer
image.png
KMP algorithm is a clever method to always avoid backup.
DFA is abstract string-search machine.
there are three properites:
- finite number of states (including start and halt)
- exactly one transition for each char in alphabet
-
accept if sequence of transitions leads to halt state
image.png
key differences from brute-force implementation
- need to precompute dfa[][] from pattern
-
text pointer i never decrements
image.png
How to build dfa from pattern?
match transition. if any state j and next char c == pat.charAt(j), go to j + 1
image.png
mismatch transition. if in state j and next char c != pat.charAt(j), then the last j-1 characters of input are pat[i..j-1], followed by c
image.png
java implementation
image.png
Boyer-moore
intuition is that we could scan characters in pattern from right to left
can skip as many as M text chars when finding one not in the pattern
image.png
how much to skip?
we could precompute index of rightmost occurrence of character c in pattern (-1 if character not in pattern)
image.png
image.png
best case N / M
worst case M * N
image.png
but we can improve worst case to 3N character compares by adding a KMP-like rule to guard against repetive patterns
Rabin-Karp
compute a hash of pattern character 0 to M - 1
for each i, compute a hash of text characters i to M + i - 1
if pattern hash = text substring hash, check for a match
image.png
image.png
image.png
Monte carlo version: return match if hash match
Las Vagas version: check for substring match if hash match; continue search if false collision
Key properties
Theory. if Q is a sufficiently large random prime (about M*N^2) then the probability of a false collision is about 1 / N
Choose Q to be large prime under reasonable assumptions, probability of a collision is about 1 / Q
if we choose monte carlo version:
always run in linear time;
extremely likely to return correct answer (but not always!)
las vagas version:
always returns correct answer
extremely likely to run in linear time (but worst case is M * N)
Advantages.
Extends to 2d patterns.
Extends to finding multiple patterns.
Disadvantages.
Arithmetic ops slower than char compares.
Las Vegas version requires backup.
Poor worst-case guarantee.
add extra credit to extend Rabin-Karp to efficiently search for any
one of P possible patterns in a text of length N
image.png
QUIZ
Q1 Cyclic rotation of a string
image.png
we append same string on the origin string. eg. 'abc' -> 'abcabc' then run KMP to check other str in substring of 'abcabc' and same length with 'abc'
Q2 Tandem repeat
image.png
mark base string as long as possible but less equal than string s, then use kmp to find the maxJ, after we can the maxJ, we can get the answer by maxJ divided by base string length.
Q3 Longest palindromic substring
image.png
nlogn solution is using karp-rabin and binary search. the thing we could know, longer palindromic string contains shorter palindromic string. thus binary search could used. if we cannot find palindromic string, we need to end = mid - 1; if we can find palindromic string, we could try longer, start = mid + 1;
the important thing we need to check odd and even number both in one binary search.
the next thing we need to design an algorithm to given a length L, check palindromic exists or not. this could solved by karp-rabin.
another hard point is that we could not use divide operation, because it will loss accuracy. what should maintain is two base. details see the code.
O(n) solution also called manacher algorithm.
https://mp.weixin.qq.com/s/EiJum3-44TqXZN4apuSQUQ
Project Boggle Game
this project is to combine the TRIE and DFS together.
foreach DFS, we have a Trie Node related to this level search.
so the possible progress step is first familiarize yourself with the BoggleBoard.java
then create boggle solver, to dfs to enumerate all string that can be composed by following sequences of adjacent dice.when the current path corresponds to a string that is not a prefix of any word in the dictionary, there is no need to expand the path further.
in the end, Deal with the special two-letter sequence Qu.
for the bonus
Make sure that you have implemented the critical backtracking optimization described above. means when next trie node is null. no need to dfs more.
Recall that the alphabet consists of only the 26 letters A through Z. use trie 26, more space but faster than TNT
it is usually almost identical to the previous prefix query, except that it is one letter longer. no need to write prefix query, just keep the state TrieNode, and current board position in each dfs.
Precompute the Boggle graph, i.e., the set of cubes adjacent to each cube. But don't necessarily use a heavyweight Graph object. y,x to caculate the key for every point, which means key = y * width + x, then for every point, save current key's neighbors key in int[][] graph , therefore we need a letter array to map the key to the letter in board. (0.85x -> 0.5x)
saved a string field in TrieNode, when meet a TrieNode string field is not null, saved it in bag (implemented in first version)
saved a sign for current call id, every call should increase this id, to know this word already been added. instead of using a set. (implemented in first version )
check dictionary words during build the trie tree , if Q is not valid, just continue it. i do not saved TrieNode u as Q's child. because in board, there only exists Qu, not any Qx. (0.5x -> 0.4x)
course quiz and project : https://github.com/yixuaz/algorithm4-princeton-cos226
