python - Runtime of brute force string-matching algorithm -


i've written small, quick (to write, not run!), algorithm string matching in python:

def brutematch(n,m):     in range(0,len(n)-len(m)+1):         if n[i:len(m)+i]==m:             return(i)

would runtime algorithm o(nm)? i'm comparing worst-case runtime horspool string-matching algorithm, (nm). guess confusion stems fact algorithm appears o(n) runtime iterates through input n, using indices inputs slice notation equality statement? thoughts?

worst case o(nm), yes. because, see, == test tests each character in each string, take long length of shortest string in equality test.


Comments

Post a Comment

Popular posts from this blog

hibernate - How to load global settings frequently used in application in Java -

1) in application have table stores settings detail used heavily every functionality.basically conditions set in table checked. now doing making db call every , fetch details , check condition.this has resulted in lot of db calls , repetitive calls same condition.there quite lot of condition records in table.we need change make perform better. 2) in previous project had same requirement have configuration table such settings configured,there implemented load configuration table @ start of application , store them in system.setproperty(name,value)..and later use system.getproperty(name) retrieve it.in case settings changed update in system property.this worked charm. however,in current case(point 1 above) don't think prev way best way because lot of records present in table having lot of columns. can suggest way how achieve such kind of behavior in java? of them can think of is 1) using system.setproperty explained. 2) using caching ehcache - standalone or hibernate(as u...
Read more

python 3.x - Mapping specific letters onto a list of words -

can please suggest approach write piece of codes automatically maps letter in letter_str onto dic_key (a dict key string type contains dashes match length of words in word_lst)? so, mapping occurs if letter appears in every words in list @ same position no matter how many words in list. if no letter appears @ position words in word list new_dic_key '----'. please see examples below thanks word_lst = ['ague', 'bute', 'byre', 'came', 'case', 'doze'] dic_key = '----' letters_str ='abcdefghijklmnopqrstuvwxyz' new_dic_key = '---e' if word_list = ['bute', 'byre'] new_dic_key = 'b--e' or word_list = ['drek', 'drew', 'dyes'] new_dic_key = 'd-e-' if words in word_list of same length code give want: word_list = ['drek', 'drew', 'dyes'] cols = [] in range(len(word_list[0])): cols.append([]) word in ...
Read more

objective c - Ownership modifiers with manual reference counting -

what happens when use objective-c onwership modifiers ( __strong, __weak, __unsafe_unretained ) manual reference counting? of them modify behavior of ignored? clang -e -dm shows definitions of built-in macros: $ clang -e -dm -x objective-c /dev/null | egrep "weak|strong|unsafe" #define __strong #define __unsafe_unretained #define __weak __attribute__((objc_gc(weak))) as can see, __strong , __unsafe_unretained defined empty macros, , __weak defined (as understand it) relevant in (no longer supported) garbage-collected environment. so in short: ownership modifiers ignored manual reference counting. makes sense because your responsibility maintain reference counts. the situation different properties: @property(strong) id x; // same "retain" @property(weak) id y; // syntax error mrc @property(unsafe_unretained) id z; // same "assign" and sake of completeness: arc ownership modifiers built-in macros de...
Read more