python string match time complexity
Question: 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 `fn =
fn[index+1 ::]`

    
    
    #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") 
    

Here is my algorithm:

  1. s in subStr: 
     * The loop starts at: "string_expression_matcher.cc"
     * The remaining string output of this step is: "tring_expression_matcher.cc"
  2. t in subStr 
     * The loop starts at: "tring_expression_matcher.cc"
     * The remaining is: "ring_expression_matcher.cc"
  3. x in subStr 
     * The loop starts at: "ring_expression_matcher.cc"
     * The remaining is: "pression_matcher.cc"
  4. p in subStr 
     * The loop starts at: "pression_matcher.cc"
     * The remaining is: "ression_matcher.cc"

and so on to last step.

Given:

    
    
    n = len(subStr)
    m = len(string)`
    

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

Does anyone know how python string copy works? what happen when we do fn =
fn[index+1 ::]?

I asked a distinguish engineer. he said the result is O(m*n). how about you?


Answer: Your algorithm (in terms of number of comparisons) is `O(n)`, where `n` is
length of the string. In the worst case both string and pattern will be the
same and then for every character in `subStr` you will move to next character
of `string`. It'll be equivalent to simple comparison of strings.

However your implementation may be `O(n^2)` in terms of other operations and
the reason for this, as you mentioned in you question, is the following line:

    
    
    fn = fn[index+1 ::]
    

This is effectively copying the string (assuming the slice above is
implemented as a copy). If you consider previous example again, for every
character in a string you'd have to copy all remaining characters, which is
`O(n^2)`. This is because you'll be copying `n-1` characters first, then
`n-2`, `n-3` and so on, and at the last iteration you will copy just one
character. Total amount of items to be copied will be then
`n-1`+`n-2`+`...`+`1`, which, as the [arithmetic
progression](http://en.wikipedia.org/wiki/Arithmetic_progression), is equal to
`(n-1)*((n-1)+1)/2 = (n-1)*n/2 = O(n^2)`. For other situations this could be
generalised to `O(m*n)`, where `m` is length of the pattern.

What your friend might like to tell you was: your algorithm is linear, but
your implementation is not. It can be easily solved though. Use solution
presented by @thkang or something more transparent to get rid of hidden
complexity, for example:

    
    
    try:
      si = iter(string)
      for c in subStr:
        while c != si.next():
          pass
    except StopIteration:
      print "no match"
    else:
      print "match"
    

