1
$\begingroup$

I'm trying to solve following problem:

Check, if the string contains substring, that can be obtained from pattern using one to one lower case symbols replacement (using bijection between original lower case letters and new letters).

My strings only consist of upper case and lower case english alphabet letters (A–Z, a–z) .

For example:

Positive:
string: justanexampleXstring
pattern: onecompleX
answer: true (anexampleX <-> onecompleX, used mapping: a<->o, x<->c; uppercase is not affected by mapping)
Negative:
string: AaBbDd
pattern: AaBa
answer: false (two repeated lower case letters in pattern and no repeated lower case letters in original string)

Currently I'm thinking about utilizing Rabin–Karp algorithm in multiple pattern search setup:

A naïve way to search for k patterns is to repeat a single-pattern search taking O(n+m) time, totaling in O((n+m)k) time. In contrast, the above algorithm can find all k patterns in O(n+km) expected time, assuming that a hash table check works in O(1) expected time.

But naïve check of strings generated by all possible mappings leads to k=26! (factorial, number of all possible one to one mappings between 26 letters alphabet)

Any ideas or optimizations to current approach would be appreciated. Thank you in advance!

$\endgroup$
3
  • 1
    $\begingroup$ You dont need to check all $k!$ bijections, simply because if you are trying to match a particular substring to the pattern - the bijection is constructed by mapping the $i$'th letter in the substring to the $i$'th letter in the pattern. Then, you only have to check that this is indeed a bijection: if it is, accept this as a correct substring, and otherwise continue to search. $\endgroup$
    – nir shahar
    Nov 3 '21 at 0:14
  • $\begingroup$ Cross-posted from StackOverflow, where it has an accepted answer. $\endgroup$
    – rici
    Nov 6 '21 at 2:02
  • $\begingroup$ I’m voting to close this question because it was cross-posted. Please do not post the same question on multiple sites. $\endgroup$
    – D.W.
    Nov 6 '21 at 9:13