title: python string match time complexity
body: <p>I need help for this question. I think the time complexity is O(n), but my friend insists that this is O(n^2). one of reason is because of <code>fn = fn[index+1 ::]</code> </p>
  
  <pre><code>#filename: string_expression_matcher.cc
  #string: stxpm.c
  #should return
  
  
  
  import sys
  string = "string_expression_matcher.cc"
  subStr = "stxpm.c"
  
  fn = list(string)
  for i in subStr:
      try:
          index = fn.index(i)
          fn = fn[index+1 ::]
      except:
          print ("can't dup")
          sys.exit()
  
  print ("found") 
  </code></pre>
  
  <p>Here is my algorithm:</p>
  
  <ol>
  <li>s in subStr:
  <ul>
  <li>The loop starts at: "string_expression_matcher.cc"</li>
  <li>The remaining string output of this step is: "tring_expression_matcher.cc"</li>
  </ul></li>
  <li>t in subStr
  <ul>
  <li>The loop starts at: "tring_expression_matcher.cc"</li>
  <li>The remaining is: "ring_expression_matcher.cc"</li>
  </ul></li>
  <li>x in subStr
  <ul>
  <li>The loop starts at: "ring_expression_matcher.cc"</li>
  <li>The remaining is: "pression_matcher.cc"</li>
  </ul></li>
  <li>p in subStr
  <ul>
  <li>The loop starts at: "pression_matcher.cc"</li>
  <li>The remaining is: "ression_matcher.cc"</li>
  </ul></li>
  </ol>
  
  <p>and so on to last step.</p>
  
  <p>Given:</p>
  
  <pre><code>n = len(subStr)
  m = len(string)`
  </code></pre>
  
  <p>what is time complexity in this program?
  Thanks for everyone, but i really want to know if O(n) or O(n^2). I know the code is not perfect but please focus on time complexity..
  Thanks so much </p>
  
  <p>Does anyone know how python string copy works? what happen when we do fn = fn[index+1 ::]?</p>
  
  <p>I asked a distinguish engineer. he said the result is O(m*n). how about you?</p>