Algorithm - String matching based on repetition factors

Question

I have three strings as the input (A,B,C).

A = "SLOVO", B = "WORD", C =

enter image description here

And I need to find algorithm which decide, if the string C is a concatenation of infinite repetiton strings A and B. Example of repetition: A^2 = "SLOVOSLOVO" and in the string C is first 8 letters "SLOVOSLO" from "SLOVOSLOVO". String B is similar.

My idea for algorithm:

index_A = 0; //index of actual letter of string A
index_B = 0;

Go throught the hole string C from 0 to size(C)
{
  Pick the actual letter from C (C[i])
  if(C[i] == A[index_A] && C[i] != B[index_B])
  {
   index_A++;
   Go to next letter in C 
  }
  else if(C[i] == B[index_B] && C[i] != A[index_A])
  {
   index_B++;
   Go to next letter in C 
  }
  else if(C[i] == B[index_B] && C[i] == A[index_A])
  {
   Now we couldn´t decice which way to go, so we should test both options (maybe recusrsion)
  }
  else
  {
   return false;
  }
}

It´s only quick description of the algorithm but I hope you understand main idea of this algorithm should do. Is this the way of solving this problem good? Do you have better solution? Or some tips?

Finally in pseudocode or probably in C. Sorry, that I write the code in "not language" but I hope you understand it. — Pepa Zapletal
– Pepa Zapletal, Commented May 12, 2014 at 16:44

Bergi · Accepted Answer · 2014-05-12 18:35:52Z

2

Basically you've got the problem that every regular expression matcher has. Yes, you would need to test both options, and if one doesn't work you will have to backtrack to the other. Expressing your loop over the string recursively can help here.

However, there is also a way to try both options at the same time. See the popular article Regular Expression Matching Can Be Simple And Fast for the idea - you basically keep track of all possible positions in the two strings during the iteration of c. The required lookup structure would have a size of len(A)*len(B), as you can just use a modulus for the string position instead of storing the position in the infinite, repeated string.

// some (pythonic) pseudocode for this:

isIntermixedRepetition(a, b, c)
    alen = length(a)
    blen = length(c)
    pos = new Set() // to store tuples
                    // could be implemented as bool array of dimension alen*blen
    pos.add( [0,0] ) // init start pos
    for ci of c
        totest = pos.getContents() // copy and
        pos.clear()                // empty the set
        for [indexA, indexB] of totest
            if a[indexA] == ci
                pos.add( [indexA + 1 % alen, indexB] )
            // no else
            if b[indexB] == ci
                pos.add( [indexA, indexB + 1 % blen] )
        if pos.isEmpty
            break
    return !pos.isEmpty

edited May 12, 2014 at 18:35

answered May 12, 2014 at 16:50

Bergi

671k162 gold badges1k silver badges1.5k bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Pepa Zapletal Over a year ago

What do you mean with "try both options at the same time" and "keep track of all possible positions in the two strings"? Can you write about your idea more? I don´t fully understand it. Thx.

Bergi Over a year ago

Have you read the article I've linked? If yes, I'll try to write some example pseudo code.

Pepa Zapletal Over a year ago

Yes, I have read it. Now I know what do you mean. Can you advice me, how I can try both options at the same time in my code? Or write some quick description of pseudocode for better explenation?

Collectives™ on Stack Overflow

Algorithm - String matching based on repetition factors

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related