KMP, dynamice programming
Given two strings S and F, how many ways there are to choose arbitrary number of non-overlapping substrings of S so that each substring is equal to F. output the answer modulo 109 + 7.
let’s say the length of string S is N, and the length of string F is M.
the solution which we are going to describe will consist of two parts, the first part is to calculate an array A which we are going to define below then the second part is make use of that array to calculate the final answer.
what is that array A? it’s an array of length N such that each element can be either 0 or 1, if the substring of length M which ends at i is equal to string M then Ai is equal to 1, otherwise it’s equal to 0.
how to calculate this array? this is a standard problem known as “string matching problem” which can be done by various algorithms, in particular it can be done in O(N+M) using KMP algorithm.
now after we calculate that array the problem is reduced to calculating the number of sub-sequences of A such that all elements of the sub-sequence are equal to 1 and no two elements of the sub-sequence have distance from each other less than M (otherwise those two elements will correspond to overlapping substrings of string S)
to calculate the number of sub-sequences we will use dynamic programming:
let Fi means the number of sub-sequences of first i elements which have value 1 and Ai is selected.
how to calculate Fi? by definition Ai is the last element of all sub-sequences counted in Fi so where is the second-last element? it could be anywhere that have distance from i at least M so Fi = segma k from 1 to i-M (Fk) + 1, we added 1 because the sub-sequence that consist of only Ai (so there’s no second last element) should be counted. note that if Ai is 0 then Fi should be 0 because we only select elements of value 1.
calculating each value of F takes O(N) steps, and we need to calculate O(N) values, so overall complexity is O(N2), but if we notice that elements inside the sigma are always a prefix of F, then we can use cumulative prefix sums so we can calculate the sigma in O(1) and overall complexity of dynamic programming would be O(N)
Can be found here.
Can be found here.