how many distinct substrings of string A that don't contain string B as a substring

Question

How can i use the KMP algorithm for finding the number of different substring of string A that don't contain string B as substring ?

I used KMP algorithm for some another problem but coudn't find how to solve this problem with KMP.

Thanks in advance.

Answer 1

I think KMP is the easy bit in a counting problem, where you need a pretty clear head. Using KMP you can go through the characters of A in turn, and detect characters of A which end an occurrence of B. You can use this to count the number of substrings of A which contain B.

If a character of A ends an occurrence of B, then every substring ending there which starts far enough back to contain B does in fact contain B. Substrings which are too short to contain B obviously don't. So in this case you can count the number of substrings of A ending at that character which contain B.

If a character of A does not end an occurrence of B, then every substring ending there which starts far enough back to contain a previous occurrence of B does in fact contain B. So (assuming that you remember where B was last seen) you can again count the number of substrings ending at this position which contain B.

So (in time linear in the length of A plus the length of B because counting the number of substrings ending at each position is just doing some simple arithmetic) you can count the number of substrings of A which contain B. Of course, you want the number of substrings that don't contain B, but the total number of substrings of A is just a quadratic in the length of A, so that is easy too.