We can solve this task by modifying the Knuth-Morris-Pratt (KMP) string searching algorithm. Let's introduce some notation.

• We will denote corresponding words of the encrypted message with ~A[1], A[2], \dots, A[n]~. Also, ~A[x, y]~ will denote the sentence made up of words ~A[x]~ through ~A[y]~.
• ~B[1], B[2], \dots, B[m]~ will be words from the sentence of the original text, and ~B[x, y]~ sentence made up of words ~B[x]~ through ~B[y]~.
• Let matches(~A[x, x+L]~, ~B[y, y+L]~) be boolean function telling us whether ~A[x, x+L]~ can be decrypted into ~B[y, y+L]~. For example, matches(a b a, c d c) = true; matches(a b b, x y z) = false.

As in standard KMP, we will calculate the prefix function ~P[1, 2, \dots, m]~, but with slightly different meaning. ~P[x]~ will be equal to largest possible ~L~ such that:

matches(~B[1, L]~, ~B[x-L+1, x]~) = true¹

After finding ~P~, we must find ~B~ within ~A~. For each word in ~A~, we are interested in the largest suffix that corresponds to some prefix of ~B~. If we encounter a mismatch, we continue with the largest possible prefix of ~B~, which we look up in ~P~.

We must also find a way to efficiently evaluate matches function. We will transform our messages using the following transformation:

• ~T(X)[i] = -1~ if ~X[i]~ doesn't appear in ~X[1, i-1]~
• ~T(X)[i] = j~ if ~j~ is the largest index such that ~j < i~ and ~X[j] = X[i]~

By using ~A' = T(A)~ and ~B' = T(B)~, we can calculate matches in linear time which is sufficient for obtaining the maximum number of points. Total complexity is also linear.

¹ Only difference between this definition and the original one is that we use our matches function instead of standard string comparison.