Hard string problem

Revision en1, by tom, 2017-07-11 00:58:08

You are given two strings — text t and pattern p. You need to find index i such that t[i...i + p.size() - 1] and p have the largest "match value". Match value of two strings of equal length a and b is total number of such j that a[j] = b[j].

Can you do this faster than O(n2) (tricks with bitsets do not count)?

Tags #strings


  Rev. Lang. By When Δ Comment
en1 English tom 2017-07-11 00:58:08 358 Initial revision (published)