jeudi 31 mars 2016

Randomized algorithm for string matching

Question:

Given a text t[1...n, 1...n] and p[1...m, 1...m], n = 2m, from alphabet [0, Sigma-1], we say p matches t at [i,j] if t[i+k-1, j+L-1] = p[k,L] for all k,L. Design a randomized algorithm to find all matches in O(n^2) time with high probability.

Image:

enter image description here

Can someone help me understand what this text means? I believe it is saying that 't' has two words in it and the pattern is also two words but the length of both patterns is half of 't'. However, from here I don't understand how the range of [i,j] comes into play. That if statement goes over my head.

This could also be saying that t and p are 2D arrays and you are trying to match a "box" from the pattern in the t 2D array.

Any help would be appreciated, thank you!




Aucun commentaire:

Enregistrer un commentaire