Show the comparisons the naive string matcher makes for the pattern \(P = 0001\) in the text \(T = 000010001010001\).

We have \(n = 15\) and \(m = 4\). Our for loop runs from \(s = 0\) to \(s = 15 - 4 = 11\).

When \(s = 0\) we proceed as follows, terminating at \(s = 3\) because there is a mismatch of characters.

\[\begin{array}{c|lc} s & P_s & T_s \\ \hline 0 & 0 & 0 \\ 1 & 0 & 0 \\ 2 & 0 & 0 \\ 3 & 1 & \require{cancel}\cancel{0} \end{array}\]

When \(s = 1\) we do not terminate because all four characters match, therefore the first pattern match occurs with shift \(1\).

\[\begin{array}{c|lc} s & P_s & T_s \\ \hline 1 & 0 & 0 \\ 2 & 0 & 0 \\ 3 & 0 & 0 \\ 4 & 1 & 1 \end{array}\]

We continue as such:

\[\begin{align*} s_2 &: \begin{array}{c|lc} s & P_s & T_s \\ \hline 2 & 0 & 0 \\ 3 & 0 & 0 \\ 4 & 0 & \require{cancel}\cancel{1} \end{array} \\ s_3 &: \begin{array}{c|lc} s & P_s & T_s \\ \hline 3 & 0 & 0 \\ 4 & 0 & \require{cancel}\cancel{1} \\ \end{array} \\ s_4 &: \begin{array}{c|lc} s & P_s & T_s \\ \hline 4 & 0 & \require{cancel}\cancel{1} \\ \end{array} \\ s_5 &: \begin{array}{c|lc} s & P_s & T_s \\ \hline 5 & 0 & 0 \\ 6 & 0 & 0 \\ 7 & 0 & 0 \\ 8 & 1 & 1 \end{array} \end{align*}\]

We now have our second pattern match at shift \(5\).

\[\begin{align*} s_6 &: \begin{array}{c|lc} s & P_s & T_s \\ \hline 6 & 0 & 0 \\ 7 & 0 & 0 \\ 8 & 0 & \require{cancel}\cancel{1} \end{array} \\ s_7 &: \begin{array}{c|lc} s & P_s & T_s \\ \hline 7 & 0 & 0 \\ 8 & 0 & \require{cancel}\cancel{1} \\ \end{array} \\ s_8 &: \begin{array}{c|lc} s & P_s & T_s \\ \hline 8 & 0 & \require{cancel}\cancel{1} \\ \end{array} \\ s_9 &: \begin{array}{c|lc} s & P_s & T_s \\ \hline 9 & 0 & 0 \\ 10 & 0 & \require{cancel}\cancel{1} \\ \end{array} \\ s_{10} &: \begin{array}{c|lc} s & P_s & T_s \\ \hline 10 & 0 & \require{cancel}\cancel{1} \\ \end{array} \\ s_{11} &: \begin{array}{c|lc} s & P_s & T_s \\ \hline 11 & 0 & 0 \\ 12 & 0 & 0 \\ 13 & 0 & 0 \\ 14 & 1 & 1 \end{array} \end{align*}\]

On the last iteration of our loop, we find the third pattern match with shift \(11\).