"""Original Unicode-codepoint multi-pattern automaton and finite oracle."""
from collections import deque
from itertools import product,combinations
import json
def build(patterns):
 if type(patterns) is not list or not 1<=len(patterns)<=8 or any(type(p) is not str or not 1<=len(p)<=8 for p in patterns) or len(set(patterns))!=len(patterns):raise ValueError('one to8 distinct nonempty bounded strings')
 nodes=[{'next':{},'fail':0,'out':[]}]
 for pid,p in enumerate(patterns):
  s=0
  for c in p:
   if c not in nodes[s]['next']:
    nodes[s]['next'][c]=len(nodes);nodes.append({'next':{},'fail':0,'out':[]})
   s=nodes[s]['next'][c]
  nodes[s]['out'].append(pid)
 q=deque(nodes[0]['next'].values())
 while q:
  s=q.popleft()
  for c,t in nodes[s]['next'].items():
   q.append(t);f=nodes[s]['fail']
   while f and c not in nodes[f]['next']:f=nodes[f]['fail']
   nodes[t]['fail']=nodes[f]['next'].get(c,0)
   nodes[t]['out']=sorted(nodes[t]['out']+nodes[nodes[t]['fail']]['out'])
 return nodes
def search(text,patterns,trace=False):
 if type(text) is not str or len(text)>32:raise ValueError('bounded literal text')
 nodes=build(patterns);s=0;hits=[];steps=[]
 for i,c in enumerate(text):
  before=s;fallback=[]
  while s and c not in nodes[s]['next']:
   t=nodes[s]['fail'];fallback.append([s,t]);s=t
  s=nodes[s]['next'].get(c,0)
  for pid in nodes[s]['out']:hits.append({'pattern_id':pid,'start':i+1-len(patterns[pid]),'end_exclusive':i+1})
  if trace:steps.append({'index':i,'char':c,'before':before,'fallback':fallback,'state':s,'output_ids':nodes[s]['out'][:]})
 return sorted(hits,key=lambda h:(h['end_exclusive'],h['pattern_id'])),nodes,steps
def oracle(text,patterns):
 return sorted([{'pattern_id':i,'start':j,'end_exclusive':j+len(p)} for i,p in enumerate(patterns) for j in range(len(text)-len(p)+1) if text[j:j+len(p)]==p],key=lambda h:(h['end_exclusive'],h['pattern_id']))
def demo():
 patterns=['اب','باب','ب','ابا'];text='بابابا';hits,nodes,trace=search(text,patterns,True);assert hits==oracle(text,patterns)
 assert any(len(x['output_ids'])>1 for x in trace) and any(x['fallback'] for x in trace)
 alphabet=['a','b','aa','ab','ba','bb'];checks=0
 for mask in range(1,1<<6):
  pats=[p for i,p in enumerate(alphabet) if mask&(1<<i)]
  for n in range(6):
   for t in product('ab',repeat=n):
    s=''.join(t);assert search(s,pats)[0]==oracle(s,pats);checks+=1
 uni=search('یيی',['ی','ي'])[0];assert [h['pattern_id'] for h in uni]==[0,1,0]
 rejected=[]
 for p in [[],[''],['a','a'],[True],['x'*9]]:
  try:build(p)
  except ValueError:rejected.append(repr(p))
  else:raise AssertionError('expected rejection')
 return {'patterns':patterns,'text':text,'index_unit':'Unicode codepoint, zero-based, end excluded; no normalization','states':nodes,'scan':trace,'all_hits':hits,'direct_slice_oracle_equal':True,'exhaustive_pattern_sets':63,'exhaustive_texts_each':63,'finite_pair_checks':checks,'unicode_literal_hits':uni,'empty_text_hits':search('',patterns)[0],'duplicate_pattern_policy':'reject','rejected':rejected,'semantic_or_product_search_claimed':False}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=True,indent=2))