Simple string matching algorithm: Difference between revisions

Revision as of 09:51, 1 October 2014

Algorithmic problem: One-dimensional string matching

Prerequisites:

Type of algorithm: loop

Auxiliary data A FIFO queue [math]\displaystyle{ I }[/math] of natural numbers, which always contains the start indexes of all occurrences of [math]\displaystyle{ T }[/math] in [math]\displaystyle{ S }[/math] that have been seen only partially thus far.

Abstract view

Induction basis

Induction step

Complexity

Further information

@@ Line 1: / Line 1: @@
-<div class="plainlinks" style="float:right;margin:0 0 5px 5px; border:1px solid #AAAAAA; width:auto; padding:1em; margin: 0px 0px 1em 1em;">
+__NOTOC__
-<div style="font-size: 1.8em;font-weight:bold;text-align: center;margin:0.2em 0 1em 0">Simple string<br>matching algorithm</div>
+[[Category:Algorithm]]
+[[Category:Main Algorithm]]
+'''Algorithmic problem:''' [[One-dimensional string matching]]
-<div style="font-size: 1.2em; margin:.5em 0 1em 0; text-align:center">whatever</div>
+'''Prerequisites:'''
-<div style="font-size: 1.2em; margin:.5em 0 .5em 0;text-align:center">[[File:olw_logo1.png|20px]][https://openlearnware.tu-darmstadt.de/#!/resource/simple-string-matching-1949 Openlearnware]</div>
+'''Type of algorithm:''' loop
-</div>
+'''Auxiliary data''' A [[FIFO queue]] <math>I</math> of natural numbers, which always contains the start indexes of all occurrences of <math>T</math> in <math>S</math> that have been seen only partially thus far.
+==Abstract view==
+==Induction basis==
+==Induction step==
+==Complexity==
+==Further information==