I want to find the number of strings that are lexicographically smaller than A and has substring B NOTE: the length of the strings should be <= |A|.
e.g. A = "da" and B = "c" then answer = 29: {'c', 'ac', 'bc', cX}, where X is any alphabet. also, constraints are pretty low, 1 <= |B|,|A| <= 1000 Please help thanks.
Does "contains" mean "subsequence" or "substring"? Is "smaller" lexicographically smaller or anything else?
it means substring, and smaller means lexicographically smaller
Is the number of such strings not infinite in your case? "c", "ca", "caa", "caaa", "caaaa" etc all have "c" as a substring and are lexicographically smaller than "da".
Oh, then the length of the strings should be <= |A|.
is there a name for this type of ordering cause I think I'm not phrasing it correctly?
I don't think it has a standard name, you just had to be more explicit.
Anyway, I think your problem can be solved with dynamic programming, states like this: $$$\mathrm{dp}[i][j][a][b]$$$ counts the number of strings lexicographically smaller than $$$A$$$, where:
I think you should be able to do updates in a KMP-like way.