Commitabc6fb2

shengshijun

committed

update README

kmp算法

1 parent0cd9ba1 commitabc6fb2Copy full SHA for abc6fb2

File tree

+42

-2

lines changed

+42

-2

lines changed

Lines changed: 1 addition & 2 deletions

Lines changed: 41 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,41 @@`
	`1`	`+#!/usr/bin/env python`
	`2`	`+# -*- coding:UTF-8`
	`3`	`+__author__='shenshijun'`
	`4`	`+`
	`5`	`+`
	`6`	`+defmatch(origin,pattern):`
	`7`	`+origin_len=len(origin)`
	`8`	`+pattern_len=len(pattern)`
	`9`	`+`
	`10`	`+defbuild_next():`
	`11`	`+_next_list= [0forxinxrange(pattern_len)]`
	`12`	`+last_match=0`
	`13`	`+forcur_indexinxrange(1,pattern_len):`
	`14`	`+whilelast_match>0andpattern[last_match]!=pattern[cur_index]:`
	`15`	`+last_match=_next_list[last_match]`
	`16`	`+ifpattern[last_match]==pattern[cur_index]:`
	`17`	`+last_match+=1`
	`18`	`+_next_list[cur_index]=last_match`
	`19`	`+return_next_list`
	`20`	`+`
	`21`	`+origin_index,pattern_index=0,0`
	`22`	`+next_list=build_next()`
	`23`	`+whileorigin_index<origin_len:`
	`24`	`+ifpattern[pattern_index]==origin[origin_index]:`
	`25`	`+pattern_index+=1`
	`26`	`+origin_index+=1`
	`27`	`+whilepattern_index>0andorigin[origin_index]!=pattern[pattern_index]:`
	`28`	`+pattern_index=next_list[pattern_index]`
	`29`	`+ifpattern_index==pattern_len:`
	`30`	`+returnorigin_index-pattern_len`
	`31`	`+`
	`32`	`+`
	`33`	`+defmain():`
	`34`	`+printmatch("sb",'sb')`
	`35`	`+`
	`36`	`+`
	`37`	`+if__name__=="__main__":`
	`38`	`+main()`
	`39`	`+`
	`40`	`+`
	`41`	`+`

Comments

(0)