Substring search

Question 1

What is the brute force approach for SS search?

Answer 1

Keep main pointer i, and pattern pointer j, for each i increment j until finding mismatch or reaching end of pattern.

Question 2

What is the alternative brute force approach?

Answer 2

If main pointer i matches j, increment j. If they do not, send i back amount of mismatches indices given by j and reset j to 0.
If fonmd, return main i - pattern length

Question 3

What is the worst case for brute force search?

Answer 3

Requires NM compares when both pattern and text are all A’s followed by a B.
For each N-M+1 possible match, all characters are cecked against text.

Question 4

How do you search manually with KMP?

Answer 4

If mismatch, find prefix that is also suffix and allign with next occurance in text.

Question 5

What are the steps for the RKF?

Answer 5

1. Compute hash value for pattern
2. Compute tvalue of R^(M-1)mod Q
3. Use hashSearch():
   * Compuite hash function for first M chars and compare against pattern hash
   * If not match, proceed through text and compute

Question 6

How does the RKM work?

Answer 6

Hash = tiR^(m-1) +…+ t(i+m-1)R^0
For the next position, we can calculate this by subtracting the contribution of the first character, times it with R and add the contribution of the next. We then mod this with Q. This computation is done in constant time.