\myheading{The \ac{DFA} version}

\leveldown{}

I reworked \href{https://algs4.cs.princeton.edu/53substring/KMP.java.html}{the Java code} by Robert Sedgewick
from \href{https://algs4.cs.princeton.edu/home/}{his excellent book}, and rewritten it to Python:

\begin{lstlisting}[style=custompy]
#!/usr/bin/env python3

def KMP(pat):
    R=256
    m=len(pat)

    # build DFA from pattern
    # https://stackoverflow.com/questions/2397141/how-to-initialize-a-two-dimensional-array-in-python
    dfa=[[0]*m for r in range(R)]
    dfa[ord(pat[0])][0]=1
    x=0
    for j in range(1, m):
        for c in range(R):
            dfa[c][j] = dfa[c][x]      # Copy mismatch cases. 
        dfa[ord(pat[j])][j] = j+1      # Set match case. 
        x = dfa[ord(pat[j])][x]        # Update restart state. 

    return dfa

# https://stackoverflow.com/questions/3525953/check-if-all-values-of-iterable-are-zero
def all_elements_in_list_are_zeros (l):
    return all(v==0 for v in l)

def export_dfa_to_graphviz(dfa, fname):
    m=len(dfa[0]) # len of pattern
    f=open(fname,"w")
    f.write("digraph finite_state_machine {\n")
    f.write("rankdir=LR;\n")
    f.write("\n")
    f.write("size=\"8,5\"\n")
    f.write(f"node [shape = doublecircle]; S_0 S_{m};\n")
    f.write("node [shape = circle];\n")

    for state in range(m):
        exits=[]
        for R in range(256):
            next=dfa[R][state]
            if next!=0:
                exits.append((R,next))
        for exit in exits:
            next_state=exit[1]
            label="'"+chr(exit[0])+"'"
            s=f"S_{state} -> S_{next_state} [ label = \"{label}\" ];\n"
            f.write (s)
        s=f"S_{state} -> S_0 [ label = \"other\" ];\n"
        f.write (s)
    f.write("}\n")
    f.close()
    print (f"{fname} written")

def search(dfa, txt):
    # simulate operation of DFA on text
    m=len(dfa[0]) # len of pattern
    n=len(txt)
    j=0 # FA state
    i=0
    while i<n and j<m:
        j = dfa[ord(txt[i])][j]
        i=i+1
    if j == m:
        return i - m # found
    return n         # not found
\end{lstlisting}

I added a code to produce a graph in GraphViz format.

Now what about the 'ok' word?

\begin{figure}[H]
\centering
\frame{\includegraphics[width=0.5\textwidth]{\CURPATH/ok.png}}
\end{figure}

Another word we already know, 'eel':

\begin{figure}[H]
\centering
\frame{\includegraphics[width=0.5\textwidth]{\CURPATH/eel.png}}
\end{figure}

The 'cocos':

\begin{figure}[H]
\centering
\frame{\includegraphics[width=0.8\textwidth]{\CURPATH/cocos.png}}
\end{figure}

You see, I can translate these \ac{FA}s to Python code:

\begin{lstlisting}[style=custompy]
#!/usr/bin/env python3

def search_eel(txt):
    # simulate operation of DFA on text
    m=3 # len of pattern
    n=len(txt)
    j=0 # FA state
    i=0 # iterator for txt[]
    while i<n and j<m:
        ch=txt[i]
        if j==0 and ch=='e':
            j=1
        elif j==1 and ch=='e':
            j=2
        elif j==2 and ch=='e':
            j=2
        elif j==2 and ch=='l':
            j=3
        else:
            j=0 # reset
        i=i+1
    if j == m:
        return i - m # found
    return n         # not found
\end{lstlisting}

Do you see any similarities with the C code from the previous part \ref{KMP1}?

Yes, what we actually did, was \ac{FA}, and the 'seen' variable was used as a marker of current state.
Here we use the 'j' variable instead, but it's almost the same!
We reinvented \ac{DFA}.

The KMP algorithm creates a \ac{DFA} for each substring to be searched.
This is \textit{preprocessing}.

The \ac{DFA} is then executes on the input string, in the very same fashion like regular expression matcher.
(For a \ac{DFA} used instead of \ac{RE} matcher, see also another example in this book: \ref{RE_DFA}.
And also: \ref{DFA_prime}.)

\myheading{All the files used}

\url{\RepoURL/\CURPATH/files_2}

\levelup{}