BVB Source Codes

Algorithm-Implementations Show kmp_match.py Source code

Return Download Algorithm-Implementations: download kmp_match.py Source code - Download Algorithm-Implementations Source code - Type:.py
  1. #!/usr/bin/env python
  2. # -*- coding: utf-8 -*-
  3.  
  4. '''
  5. File: kmp_match.py
  6. Author:
  7. Description: http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm and the Author: Keith Schwarz (htiek@cs.stanford.edu)
  8. '''
  9.  
  10.  
  11. def failTable(pattern):
  12.     '''Create the resulting table, which for length zero is None.
  13.    Usage:
  14.    >>>failTable('ABCDABD')
  15.    [None, 0, 0, 0, 0, 1, 2, 0]
  16.    >>>failTable('py py py python py')
  17.    [None, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 0, 0, 0, 0, 1, 2]
  18.    '''
  19.     result=[None]
  20.  
  21.     # Iterate across the rest of the characters, filling in the values for the
  22.     # rest of the table.
  23.     for i in range(len(pattern)):
  24.         j = i
  25.  
  26.         while True:
  27.             # If j hits zero, the recursion says that the resulting value is
  28.             # zero since we're looking for the LPB of a single-character
  29.             # string.
  30.             if j == 0:
  31.                 result.append(0)
  32.                 break
  33.  
  34.             # Otherwise, if the character one step after the LPB matches the
  35.             # next character in the sequence, then we can extend the LPB by one
  36.             # character to get an LPB for the whole sequence.
  37.             if pattern[result[j]] == pattern[i]:
  38.                 result.append(result[j] + 1)
  39.                 break
  40.  
  41.             # Finally, if neither of these hold, then we need to reduce the
  42.             # subproblem to the LPB of the LPB.
  43.             j = result[j]
  44.  
  45.     return result
  46.  
  47. def kmpMatch(needle, haystack):
  48.     fail = failTable(needle)
  49.  
  50.     # Keep track of the start index and next match position, both of which
  51.     # start at zero since our candidate match is at the beginning and is trying
  52.     # to match the first character.
  53.     index = 0
  54.     match = 0
  55.  
  56.     while index + match < len(haystack):
  57.  
  58.         # If the current character matches the expected character, then bump up
  59.         # the match index.
  60.         if haystack[index + match] == needle[match]:
  61.             match = match + 1
  62.  
  63.             # If we completely matched everything, we're done.
  64.             if match == len(needle):
  65.                 return index
  66.  
  67.         # Otherwise, we need to look at the fail table to determine what to do
  68.         # next.
  69.         else:
  70.  
  71.             # If we couldn't match the first character, then just advance the
  72.             # start index.  We need to try again.
  73.             if match == 0:
  74.                 index = index + 1
  75.  
  76.             # Otherwise, see how much we need to skip forward before we have
  77.             # another feasible match.
  78.             else:
  79.                 index = index + match - fail[match]
  80.                 match = fail[match]
  81.  
  82.     # if no match,return None
  83.     return None
  84.  
  85.  
  86. if __name__ == '__main__':
  87.  
  88.    print kmpMatch('ABCDABD', 'ABC ABCDAB ABCDABCDABDE') # 15
  89.    print kmpMatch('0101', '0011001011') # 5
  90.    print kmpMatch('py py py python py', 'apyapy py py python pys') # 4
  91.  
downloadkmp_match.py Source code - Download Algorithm-Implementations Source code
Related Source Codes/Software:
raty - 2017-04-22
RDVTabBarController - Highly customizable tabBar and tabBarController fo... 2017-04-22
material-icon-lib - Library containing over 1500 material vector icons... 2017-04-21
httpdiff - Perform the same request against two HTTP servers ... 2017-04-21
jquerytools - The missing UI library for the Web ... 2017-04-21
mcrouter - Mcrouter is a memcached protocol router for scalin... 2017-04-22
dynomite - A generic dynamo implementation for different k-v ... 2017-04-22
kityminder - Baidu brain figure 2017-04-22
llvm - Mirror of official llvm git repository located at ... 2017-04-22
RBBAnimation - Block-based animations made easy, comes with easin... 2017-04-22
ied - 2017-04-29
Nimble - A Matcher Framework for Swift and Objective-C 2017-04-29
MHVideoPhotoGallery - A Photo and Video Gallery 2017-04-29
shoulda-matchers - Collection of testing matchers extracted from Shou... 2017-04-29
Android-SlideExpandableListView - A better ExpandableListView, with animated expanda... 2017-04-29
AppSales-Mobile - App Sales allows iPhone and Mac App Store develope... 2017-04-29
react-templates - Light weight templates for react ... 2017-04-28
afterglow-theme - A minimal dark Theme for Sublime Text 2 and 3 2017-04-28
jwt-go - Golang implementation of JSON Web Tokens (JWT) 2017-04-28
DeerResume - Tool MarkDown online resume, online preview, edit,... 2017-04-28

 Back to top