Home My Page Projects Code Snippets Project Openings SML/NJ
 Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

# SCM Repository

[smlnj] Diff of /sml/trunk/src/system/smlnj/init/pre-string.sml
 [smlnj] / sml / trunk / src / system / smlnj / init / pre-string.sml

# Diff of /sml/trunk/src/system/smlnj/init/pre-string.sml

revision 1154, Wed Mar 20 20:44:43 2002 UTC revision 1155, Wed Mar 20 20:52:51 2002 UTC
# Line 190  Line 190
190              collate cmpFn (s1, i1, n1, s2, i2, n2)              collate cmpFn (s1, i1, n1, s2, i2, n2)
191            end            end
192
193        (* Knuth-Morris-Pratt String Matching
194         *
195         * val kmp : string -> string * int * int -> int option
196         * Find the first string within the second, starting at and
197         * ending before the given positions.
198         * Return the starting position of the match
199         * or ~1 if there is no match. *)
200        fun kmp pattern =
201            let val psz = size pattern
202                val next = InlineT.PolyArray.array (psz, ~1)
203
204                fun pat x = unsafeSub (pattern, x)
205                fun nxt x = InlineT.PolyArray.sub (next, x)
206                fun setnxt (i, x) = InlineT.PolyArray.update (next, i, x)
207
208                (* trying to fill next at position p (> 0) and higher;
209                 * invariants: x >= 0
210                 *             pattern[0..x) = pattern[p-x..p)
211                 *             for i in [0..p) :
212                 *                 pattern[i] <> pattern[next[i]]
213                 *                 pattern[0..next[i]) = pattern[i-next[i]..i) *)
214                fun fill (p, x) = if p >= psz then ()
215                                  else if pat x = pat p then dnxt (p, nxt x, x + 1)
216                                  else dnxt (p, x, nxt x + 1)
217                and dnxt (p, x, y) = (setnxt (p, x); fill (p + 1, y))
218
219                (* Once next has been initialized, it serves the following purpose:
220                 * Suppose we are looking at text position t and pattern position
221                 * p.  This means that all pattern positions < p have already
222                 * matched the text positions that directly precede t.
223                 * Now, if the text[t] matches pattern[p], then we simply advance
224                 * both t and p and try again.
225                 * However, if the two do not match, then we simply
226                 * try t again, but this time with the pattern position
227                 * given by next[p].
228                 * Success is when p reaches the end of the pattern, failure is
229                 * when t reaches the end of the text without p having reached the
230                 * end of the pattern. *)
231                fun search (text, start, tsz) =
232                    let fun txt x = unsafeSub (text, x)
233                        fun loop (p, t) =
234                            if p >= psz then t - psz
235                            else if t >= tsz then ~1
236                            else if p < 0 orelse pat p = txt t then loop (p+1, t+1)
237                            else loop (nxt p, t)
238                    in loop (0, start)
239                    end
240            in fill (1, 0); search
241            end
242
243      end (* local *)      end (* local *)
244    end; (* PreString *)    end; (* PreString *)
245  end  end

Legend:
 Removed from v.1154 changed lines Added in v.1155