Brute Force Pattern Matching

"""

FOR: Vishavjeet Thakur
RE:
https://www.facebook.com/groups/860936880721980/permalink/1269063029909361/

Tested with Python 3.6.1

Searches for a pattern within a string.

Example 1
---------
Input
  String "pypropy"
Pattern
  String "aba"
Output
  1 (success)

Example 2
---------
Input
  String "aba"
Pattern
  String "xyz"
Output
  0 (failure)

The algorithm involves assigning alias symbols for
each unique character within a given substring.
The order of the alias symbols must match the order
established in the pattern string.

"""

# Set this to false for silent running
verbose_mode = True

# Used to implement verbose/silent mode
def message(msg):
  if (verbose_mode):
    print(msg)

"""
Represents a pattern (list of alias symbols)
Maps each alias symbol to a position (0-based)
"""
class Pattern:
  # Pass in a pattern string
  def __init__(self,pat):
    self.chars = [alias for alias in pat]
    self.dump()
  # Return count of alias letters
  def count(self):
    return len(self.chars)
    # Determine if alias exists in pattern
  def contains(self, alias):
    return alias in self.chars
  # Return alias char at given index
  def alias_at(self,index):
    return self.chars[index]
  # Determine if alias char matches alias at index
  def match_at(self,index,alias):
    return alias == self.chars[index]
  # Dump state to console
  def dump(self):
    message("Pattern to match: {}".format(self.chars))

"""
Represents a dictionary
Maps unique source characters to alias symbols
"""
class Mapper:
  # Constructor
  def __init__(self):
    self.chars = {}
  # Remove all characters from dictionary
  def clear(self):
    self.chars = {}
  # Return count of characters in dictionary
  def count(self):
    return len(self.chars)
  # Determine if character exists in dictionary
  def has_alias(self,char):
    return char in self.chars
  # Determine if an alias can be added
  def can_add_alias(self,alias):
    return alias not in self.chars.values()
  # Add character and its alias to dictionary
  def add_alias(self,char,alias):
    message("Adding: '{}' alias '{}'".format(char,alias))
    self.chars[char]=alias
  # Return alias for a character
  def get_alias(self,char):
    return self.chars[char]
  # Determine if character's alias matches
  def matches(self,char,alias):
    return self.chars[char] == alias
  # Return string representation
  def __str__(self):
    return str(self.chars)
  # Dump all aliases to console
  def dump(self):
    message("Mapper State:")
    for char, alias in self.chars.items():
      message("'{}' alias '{}'".format(char, alias))

"""
Prepresents an object that can
compare a substring to a pattern.
Substring size must be same as pattern size
"""
class Comparer:
  # Constructor (accepts pattern as a string)
  def __init__(self,pat):
    # Create a pattern object from string
    self.pattern = Pattern(pat)
    # Create a dictionary object for aliasing
    self.mapper = Mapper()
  # Determine if substring matches pattern
  def matches(self,source):
    # Check for length mismatch up front
    if len(source) != self.pattern.count():
      message("Error: source string too short")
      return False # Failure
    # Index into pattern list
    index = 0
    # Clear the alias dictionary
    self.mapper.clear()
    # Show substring to be compared
    message("\n----------------")
    message("Checking substring '{}'".format(source))
    # For each source character
    for ch in source:
      message("Comparing '{}'".format(ch))
      # If the char already has an alias
      if self.mapper.has_alias(ch):
        # Obtain the alias
        alias = self.mapper.get_alias(ch)
        message("Existing alias '{}'".format(alias))
        # Look up the wanted alias at this index
        wanted = self.pattern.alias_at(index)
        message("Wanted alias '{}'".format(wanted))
        # If the alias matches the pattern so far
        if alias == wanted:
          # Move to index of next alias in pattern
          index += 1
          # Go back for next character
          continue
        # The alias doesn't match
        else:
          message("Error: Alias mismatch!")
          # Return failure code
          return False
      # This character has no alias yet
      else:
        # Grab a new alias from the pattern
        alias = self.pattern.alias_at(index)
        message("Assigning new alias: '{}'".format(alias))
        # Make sure that this alias is unique
        if not self.mapper.can_add_alias(alias):
          message("Error: Duplicate!")
          return False # Failure
        # Map this alias to the character
        self.mapper.add_alias(ch,alias)
        # Move to index of next alias in pattern
        index += 1
        continue
    # Success!
    return True
  # Dump internal state to console
  def dump(self):
    message("\nComparer State:")
    self.pattern.dump()
    self.mapper.dump()


"""
Pattern matching function
"""
def matchPattern(source,pat):
  # Construct a comparer for substrings
  comp = Comparer(pat)
  # Get the pattern length
  size = len(pat)
  # Special case for zero size pattern
  if size < 1:
    return 0 # Failure
  # So long as we has enough characters remaining
  # for a possible match...
  while len(source) >= size:
    # Grab the next substring
    chunk = source[0:size]
    # Check for a match
    if comp.matches(chunk):
      message("\nMatched: {}".format(chunk))
      return 1 # Success!
    # Remove the first character from
    # the source string
    source = source[1:]
  # Failed
  comp.dump()
  return 0

# Run test case
if __name__ == "__main__":
  source = "pypropy"
  pattern = "aba"
  result = matchPattern(source, pattern)
  print("\nResult: {}".format(result))