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