import gradio as gr



# please check the course slides to get much simpler implementation
def get_pm_table(pattern):
  L = len(pattern)
  pm = [0]*L
  k = 0
  for q in range(1,L):
    if pattern[q] == pattern[k]:
      pm[q] = k + 1
      k = k + 1
    else:
      while k > 0:
        k = pm[k-1]
        if pattern[k] == pattern[q]:
          pm[q] = k + 1
          k = k + 1
          break
      
      if k == 0:
        if pattern[q] == pattern[k]:
          pm[q] = k + 1
          k = k + 1
        else:
          pm[q] = 0
  return pm



def KMP_search(pattern, string):
  m = len(pattern)
  n = len(string)

  pm = get_pm_table(pattern)
  i = 0
  q = 0
  location = []

  trial = 0
  while i < n:
    if string[i] == pattern[q]:
      i = i + 1
      q = q + 1
      if q == m:
        pos = i - q
        q = pm[q-1]
        location.append(pos+1)# set index starting from 1

        #print("Found ", string[pos:pos+m], ' locating at position ', location)
    else:
      if q ==0:
        i = i + 1
        trial += 1
        #print(trial,"-> i=",i)
        #print(string[i:i+m])
        #print(pattern)
      else:
        q = pm[q-1]
  
  return location




def search_pattern(fulltext, pattern, method):
    fulltext = fulltext.replace('\n','')
    pattern = pattern.replace('\n','')
    if method == 'Naive-Exact-Match':
        import time
        start = time.time()
        occurrence = 0
        for i in range(0,len(fulltext)-len(pattern)+1):
          found = 1
          for l in range(len(pattern)):
             if fulltext[i+l] != pattern[l]:
                 found = 0
          if found:   
             occurrence += 1
             print("Found ", fulltext[i:i+len(pattern)], ' locating at position ', i+1)
        
        end = time.time()
        time_elapse = end - start

    if method == "Knuth-Morris-Pratt":
        import time
        start = time.time()
        results = KMP_search(pattern, fulltext)
        end = time.time()
        time_elapse = end - start
        occurrence = len(results)

    return occurrence, time_elapse
    
    
### configure inputs/outputs
set_fulltext = gr.inputs.Textbox(label="Full Text")
set_pattern = gr.inputs.Textbox(label="Pattern")
set_method = gr.Radio(["Naive-Exact-Match", "Knuth-Morris-Pratt"])
set_results = gr.outputs.Textbox(label="Occurrence")
set_times = gr.outputs.Textbox(label="Time elapse")


### configure gradio, detailed can be found at https://www.gradio.app/docs/#i_slider
interface = gr.Interface(fn=search_pattern, 
                         inputs=[set_fulltext, set_pattern,set_method], 
                         outputs=[set_results,set_times],
                         examples_per_page = 2,
                         title="BCB5300 Demo 1: Sequence Match", 
                         theme = 'huggingface',
                         layout = 'vertical'
                         )
                      
interface.launch(debug=True)