"""
This module executes the string matching between a input sequence T and an
pattern P using a Finite State Machine.
The complexity for building the transition function is O(m^3 x |A|) where A is the
alphabet. Since the string matching function scan the input sequence only once,
the total complexity is O(n + m^3 x |A|)

@author Filippo Squillace
@version 1.0.0
@date 07/06/2012

"""

def string_matching_FSM(T, trans, m):
    """
    T: is the input sequence;
    trans: is the transition function that define the pattern P we need to look
    for;
    m: lenght of the pattern
    """
    s = 0
    for i,c in enumerate(T):
        s = trans[s][c]
        if s == m:
            return i-m+1

    return -1

import string as st
def transition_function(P):
    """
    The main principle on building the transition function is to think about
    the fact that every time we scan a new character from the input sequence
    the suffix should match with the prefix of the pattern. If that is not
    possible for every length of the suffix, the next state need to be the
    initial, otherwise the length of the suffix that matches properly will be
    exactly the next state.
    """
    alphabet = st.ascii_letters+st.punctuation+st.digits+st.whitespace
    m = len(P)
    trans = [{c:0 for c in alphabet} for i in range(m)]
    for s in range(m):
        for c in alphabet:
            k = min(m, s+1)
            while (P[:s]+c)[-k:] != P[:k]:
                k-=1

            trans[s][c]=k

    return trans



if __name__=='__main__':
    import unittest
    class StringMatchTestCase(unittest.TestCase):
        def setUp(self):
            # Table of (sequence,pattern,expected_result)
            self.pos_cases = [\
                    ('abcbbaanmdiababcdrttf','ababcd',11),
                    ('abcbbaanmdiabafweefabab','abab',19),
                    ('abcbbaanmdiasfo pfj=pewpfiojafaXre8abbafw_ eefabab','aXre8ab',30)
                    ]

            self.neg_cases = [\
                    ('abcbbaanmdiabcdrttf','ababcd',-1),
                    ('abcbbaanmdiabafweefaba','abab',-1),
                    ('abcbb_?aaFSRnmfew345sdhfhhuw.fad iabafweefaba','abab',-1)
                    ]

        def test_positive(self):
            for (T,P,er) in self.pos_cases:
                trans = transition_function(P)
                res = string_matching_FSM(T, trans, len(P))
                self.assertEqual(res, er)

        def test_negative(self):
            for (T,P,er) in self.neg_cases:
                trans = transition_function(P)
                res = string_matching_FSM(T, trans, len(P))
                self.assertEqual(res, er)

    unittest.main()