"""Authored KMP prefix/fallback and overlapping exact Unicode codepoint matches."""
import itertools,json
def prefix(p):
    pi=[0]*len(p)
    for i in range(1,len(p)):
        j=pi[i-1]
        while j and p[i]!=p[j]:j=pi[j-1]
        if p[i]==p[j]:j+=1
        pi[i]=j
    return pi
def search(text,p):
    if not p:raise ValueError('nonempty pattern required by this fixture')
    pi=prefix(p);j=0;matches=[];fallbacks=[];comparisons=0
    def equal(a,b):
        nonlocal comparisons
        comparisons+=1;return a==b
    for i,c in enumerate(text):
        while j and not equal(c,p[j]):
            old=j;j=pi[j-1];fallbacks.append({'text_index':i,'character':c,'from_matched_length':old,'to_matched_length':j})
        if equal(c,p[j]):j+=1
        if j==len(p):matches.append(i-len(p)+1);j=pi[j-1]
    return {'prefix':pi,'matches_zero_based':matches,'mismatch_fallbacks':fallbacks,'actual_match_phase_character_comparisons':comparisons,'comparison_scope':'actual calls in while condition plus final if, repeated equal check counted; prefix construction and naive oracle excluded'}
def naive(text,p):return [i for i in range(len(text)-len(p)+1)if text[i:i+len(p)]==p]
def demo():
    text='abaabaabababaabab';p='abaabab';main=search(text,p);assert main['prefix']==[0,0,1,1,2,3,2]and main['matches_zero_based']==naive(text,p)
    overlap=search('aaaaa','aaa');assert overlap['matches_zero_based']==[0,1,2]
    pairs=0
    for n in range(7):
        for t in map(''.join,itertools.product('ab',repeat=n)):
            for m in range(1,4):
                for pat in map(''.join,itertools.product('ab',repeat=m)):
                    got=search(t,pat);assert got['matches_zero_based']==naive(t,pat)
                    assert got['prefix']==[max(k for k in range(i+1)if pat[:k]==pat[i-k+1:i+1])for i in range(len(pat))];pairs+=1
    assert pairs==1778
    persian='می‌رویم، می‌رویم';pat='می‌رویم';fa=search(persian,pat);assert fa['matches_zero_based']==[0,9]
    assert search('ي','ی')['matches_zero_based']==[]
    try:search('abc','')
    except ValueError:empty=True
    else:raise AssertionError('empty accepted')
    return {'authored_text':text,'pattern':p,'main':main,'overlapping':{'text':'aaaaa','pattern':'aaa','result':overlap},'independent_exhaustive_binary_text_pattern_pairs':pairs,'persian':{'text':persian,'pattern':pat,'result':fa,'offset_unit':'Unicode code points, not UTF-8 bytes or grapheme clusters'},'arabic_persian_yeh_not_implicitly_normalized':True,'empty_pattern_rejected':empty,'semantic_fuzzy_search_or_llm_executed':False}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=False,indent=2))