String Matching using Bitset

In this article, we have explored how to solve string matching problem (find all occurences of string S1 in another string S2) using Bitset. It is a modification of the naive approach which takes O(L x P x logL) time complexity and assumes all positions to be potential matches and eliminates them based on previous comparisons. The modification with bitset improves the time complexity to O(L x P / K) where L is length of string S2, P is length of string S1 and K is register size.

Bitset

Bitset i...