Search code examples
algorithmsortingpermutation

Algorithm - find all permutations of string a in string b

Say we have

string a = "abc"
string b = "abcdcabaabccbaa"

Find location of all permutations of a in b. I am trying to find an effective algorithm for this.

Pseudo code:

sort string a // O(a loga)

for windows of length a in b  // O(b)?
   sort that window of b      // O(~a loga)?
   compare to a
   if equal
      save the index

So would this be a correct algorithm? Run time would be around O(aloga + ba loga) ~= O(a loga b)? How efficient would this be? Possibly way to reduce to O(a*b) or better?

Solution

  • sorting is very expensive, and doesn't use the fact you move along b with a sliding window.

    I would use a comparison method that is location agnostic (since any permutation is valid) - assign each letter a prime number, and each string will be the multiplication of its letter values.

    this way, as you go over b, each step requires just dividing by the letter you remove from he left, and multiplying with the next letter.

    You also need to convince yourself that this indeed matches uniquely for each string and covers all permutations - this comes from the uniqueness of prime decomposition. Also note that on larger strings the numbers get big so you may need some library for large numbers