Basic string position search method
Python uses the variable .find("what to find" [, start position, end position]) to find a string. The start position and end position represent the range to be searched. If it is empty, it means to search all. After the search is found, the position will be returned. The position is calculated from 0, and -1 will be returned every time it is found.
1 2 3 | str = 'a,hello'
print str .find( 'hello' )
>> 2
|
Copy after login
Naive Matching Algorithm
The naive matching algorithm is a one-to-one match between the target string and the template string. If there is a match, move the subscript one position to the right, otherwise clear it and start matching again.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | target = 'abb aba'
pattern = 'aba'
def match(target, pattern):
i = j = 0
n, m = len (target), len (pattern)
while i < n and j < m:
if target[i] = = pattern[j]:
i, j = i + 1 , j + 1
else :
i = i - j + 1
j = 0
if j = = m:
return i - j
return - 1
|
Copy after login
Add print to the above and print it again
1 2 3 4 5 6 7 8 9 10 11 | else :
i = i - j + 1
j = 0
print (target[i], pattern[j], i, j)
b a 1 0
b a 2 0
a 3 0
a a 4 0
|
Copy after login
The loop will continue until equal matching values. This method is inefficient, mainly because the template characters will be looped again when there is no match. It may occur up to m * (n-m 1) times. m is the length of template characters, n-m 1 is the number of times to exclude unequal characters.
KMP algorithm
kmp is an algorithm for shifting by known matching characters. For example, if abb is compared with abc above, ab is known.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | def match(target, pattern):
i = j = 0
n, m = len (target), len (pattern)
while i < n and j < m:
if if j = = - 1 and target[i] = = pattern[j]:
i, j = i + 1 , j + 1
else :
i = i - j + pattern_next(pattern[:j])
j = 0
if j = = m:
return i - j
return - 1
def pattern_next(s):
prefix = [s[:i + 1 ] for i in range ( len (s) - 1 )]
suffix = [s[i + 1 :] for i in range ( len (s) - 1 )]
l = list ( set (prefix) & set (suffix))
return len (l)
|
Copy after login
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Latest Articles by Author
-
2024-10-22 09:46:29
-
2024-10-13 13:53:41
-
2024-10-12 12:15:51
-
2024-10-11 22:47:31
-
2024-10-11 19:36:51
-
2024-10-11 15:50:41
-
2024-10-11 15:07:41
-
2024-10-11 14:21:21
-
2024-10-11 12:59:11
-
2024-10-11 12:17:31