String-Matching-Algorithmus - Versionsgeschichte

Invisigoth67: typo

2022-10-29T09:45:52Z

typo

← Nächstältere Version		Version vom 29. Oktober 2022, 11:45 Uhr
Zeile 42:		Zeile 42:
	Bei dem String-Matching-Algorithmus mit Hilfe von [[Endlicher Automat\|endlichen Automaten]] wird ein für ein Alphabet <math>\Sigma</math> und ein gegebenes Suchmuster der Länge <math>m</math> ein Automat <math>(Q, \Sigma, \delta, q_0, \{q_m\})</math> mit Zustandsmenge <math>\textstyle Q = \{q_i \mid 0 \le i \le m\}</math> erstellt. Dabei stellt <math>\textstyle i</math> die Anzahl von übereinstimmenden Buchstaben an der aktuellen Stelle vom Anfang des Suchmusters an betrachtet dar. Zur Einfachheit sei <math>\textstyle P_i</math> das [[Präfix]] des Suchmusters bis einschließlich des Buchstabens an der Stelle <math>\textstyle i</math>. Die Übergangsfunktion <math>\delta(q_i, a)</math> mit <math>a \isin \Sigma</math> gibt nun für <math>0 \le i \le m - 1</math> wieder einen Zustand <math>q_j</math> zurück, bei dem <math>j</math> die maximale Anzahl von Buchstaben darstellt, mit der <math>P_j</math> ein [[Suffix]] vom Wort <math>P_i a</math> ist. Also <math>\delta(q_i, a) = q_{max\{j \mid P_j \text{ ist Suffix von } P_i a\}}</math>. Ist das Suchmuster gefunden, wird im Endzustand verharrt, also <math>\delta(q_m, a) = q_m</math>.		Bei dem String-Matching-Algorithmus mit Hilfe von [[Endlicher Automat\|endlichen Automaten]] wird ein für ein Alphabet <math>\Sigma</math> und ein gegebenes Suchmuster der Länge <math>m</math> ein Automat <math>(Q, \Sigma, \delta, q_0, \{q_m\})</math> mit Zustandsmenge <math>\textstyle Q = \{q_i \mid 0 \le i \le m\}</math> erstellt. Dabei stellt <math>\textstyle i</math> die Anzahl von übereinstimmenden Buchstaben an der aktuellen Stelle vom Anfang des Suchmusters an betrachtet dar. Zur Einfachheit sei <math>\textstyle P_i</math> das [[Präfix]] des Suchmusters bis einschließlich des Buchstabens an der Stelle <math>\textstyle i</math>. Die Übergangsfunktion <math>\delta(q_i, a)</math> mit <math>a \isin \Sigma</math> gibt nun für <math>0 \le i \le m - 1</math> wieder einen Zustand <math>q_j</math> zurück, bei dem <math>j</math> die maximale Anzahl von Buchstaben darstellt, mit der <math>P_j</math> ein [[Suffix]] vom Wort <math>P_i a</math> ist. Also <math>\delta(q_i, a) = q_{max\{j \mid P_j \text{ ist Suffix von } P_i a\}}</math>. Ist das Suchmuster gefunden, wird im Endzustand verharrt, also <math>\delta(q_m, a) = q_m</math>.

	Der Vorteil dieses Algorithmus gegenüber dem naiven Algorithmus liegt darin, dass er auch beim ~~finden~~ eines nicht-passenden Zeichens das erlangte Wissen über den bereits verarbeiteten Teil der Zeichenkette nicht verwirft. Angenommen, wir suchen das Muster ''anax'' im Text ''ananax''. Trifft der automatenbasierte Algorithmus bei der Suche auf das Zweite ''n'' in ''<span style="color:#008000">ana</span><span style="color:#800000">n</span>ax'', so wird er die ersten beiden Buchstaben verwerfen und beginnend mit ''an<span style="color:#008000">an</span>ax'' weitersuchen. Der naive Algorithmus hingegen hätte den kompletten bereits verarbeiteten Teil verworfen und hätte beginnend mit ''a<span style="color:#008000">n</span>anax'' einen nächsten Versuch begonnen.		Der Vorteil dieses Algorithmus gegenüber dem naiven Algorithmus liegt darin, dass er auch beim Finden eines nicht-passenden Zeichens das erlangte Wissen über den bereits verarbeiteten Teil der Zeichenkette nicht verwirft. Angenommen, wir suchen das Muster ''anax'' im Text ''ananax''. Trifft der automatenbasierte Algorithmus bei der Suche auf das Zweite ''n'' in ''<span style="color:#008000">ana</span><span style="color:#800000">n</span>ax'', so wird er die ersten beiden Buchstaben verwerfen und beginnend mit ''an<span style="color:#008000">an</span>ax'' weitersuchen. Der naive Algorithmus hingegen hätte den kompletten bereits verarbeiteten Teil verworfen und hätte beginnend mit ''a<span style="color:#008000">n</span>anax'' einen nächsten Versuch begonnen.

	'''Python-Implementation'''		'''Python-Implementation'''

46.114.142.194: Komma zugefügt

2022-10-26T11:24:54Z

Komma zugefügt

← Nächstältere Version		Version vom 26. Oktober 2022, 13:24 Uhr
Zeile 23:		Zeile 23:
	'''Pseudocode:'''		'''Pseudocode:'''
	'''Eingabe''': Strings T = T<sub>1</sub>… T<sub>n</sub> und P = P<sub>1</sub> … P<sub>m</sub>		'''Eingabe''': Strings T = T<sub>1</sub>… T<sub>n</sub> und P = P<sub>1</sub> … P<sub>m</sub>
	'''Ausgabe''': q die Stellen an denen P in T auftritt		'''Ausgabe''': q die Stellen, an denen P in T auftritt

	<syntaxhighlight lang="pascal">		<syntaxhighlight lang="pascal">

Xqt: /* Siehe auch */

2019-03-10T12:33:10Z

Siehe auch

← Nächstältere Version		Version vom 10. März 2019, 14:33 Uhr
Zeile 189:		Zeile 189:
	* [[Suchverfahren]]		* [[Suchverfahren]]
	* [[Levenshtein-Distanz]] (approximative Suche)		* [[Levenshtein-Distanz]] (approximative Suche)
			* [[Gestalt Pattern Matching]] (approximative Suche)
	* [[Volltextrecherche]]		* [[Volltextrecherche]]

Facme: /* Endlicher Automat */ Grammatik

2019-02-03T07:27:45Z

Endlicher Automat: Grammatik

← Nächstältere Version		Version vom 3. Februar 2019, 09:27 Uhr
Zeile 40:		Zeile 40:
	==== Endlicher Automat ====		==== Endlicher Automat ====
	[[Datei:Eines endlicher Automat zur Suche der Zeichenkette "anax" in Texten.svg\|mini\|Ein endlicher Automat zur Suche des Wortes ''anax'']]		[[Datei:Eines endlicher Automat zur Suche der Zeichenkette "anax" in Texten.svg\|mini\|Ein endlicher Automat zur Suche des Wortes ''anax'']]
	Bei dem String-Matching-Algorithmus mit Hilfe von [[Endlicher Automat\|endlichen Automaten]] wird ein für ein Alphabet <math>\Sigma</math> und ein gegebenes Suchmuster der Länge <math>m</math> ein Automat <math>(Q, \Sigma, \delta, q_0, \{q_m\})</math> mit Zustandsmenge <math>\textstyle Q = \{q_i \mid 0 \le i \le m\}</math> erstellt. Dabei stellt <math>\textstyle i</math> die Anzahl von übereinstimmenden Buchstaben an der aktuellen Stelle vom Anfang des Suchmusters an betrachtet dar. Zur Einfachheit sei <math>\textstyle P_i</math> das [[Präfix]] des Suchmusters bis einschließlich ~~dem~~ ~~Buchstaben~~ an der Stelle <math>\textstyle i</math>. Die Übergangsfunktion <math>\delta(q_i, a)</math> mit <math>a \isin \Sigma</math> gibt nun für <math>0 \le i \le m - 1</math> wieder einen Zustand <math>q_j</math> zurück, bei dem <math>j</math> die maximale Anzahl von Buchstaben darstellt, mit der <math>P_j</math> ein [[Suffix]] vom Wort <math>P_i a</math> ist. Also <math>\delta(q_i, a) = q_{max\{j \mid P_j \text{ ist Suffix von } P_i a\}}</math>. Ist das Suchmuster gefunden, wird im Endzustand verharrt, also <math>\delta(q_m, a) = q_m</math>.		Bei dem String-Matching-Algorithmus mit Hilfe von [[Endlicher Automat\|endlichen Automaten]] wird ein für ein Alphabet <math>\Sigma</math> und ein gegebenes Suchmuster der Länge <math>m</math> ein Automat <math>(Q, \Sigma, \delta, q_0, \{q_m\})</math> mit Zustandsmenge <math>\textstyle Q = \{q_i \mid 0 \le i \le m\}</math> erstellt. Dabei stellt <math>\textstyle i</math> die Anzahl von übereinstimmenden Buchstaben an der aktuellen Stelle vom Anfang des Suchmusters an betrachtet dar. Zur Einfachheit sei <math>\textstyle P_i</math> das [[Präfix]] des Suchmusters bis einschließlich des Buchstabens an der Stelle <math>\textstyle i</math>. Die Übergangsfunktion <math>\delta(q_i, a)</math> mit <math>a \isin \Sigma</math> gibt nun für <math>0 \le i \le m - 1</math> wieder einen Zustand <math>q_j</math> zurück, bei dem <math>j</math> die maximale Anzahl von Buchstaben darstellt, mit der <math>P_j</math> ein [[Suffix]] vom Wort <math>P_i a</math> ist. Also <math>\delta(q_i, a) = q_{max\{j \mid P_j \text{ ist Suffix von } P_i a\}}</math>. Ist das Suchmuster gefunden, wird im Endzustand verharrt, also <math>\delta(q_m, a) = q_m</math>.

	Der Vorteil dieses Algorithmus gegenüber dem naiven Algorithmus liegt darin, dass er auch beim finden eines nicht-passenden Zeichens das erlangte Wissen über den bereits verarbeiteten Teil der Zeichenkette nicht verwirft. Angenommen, wir suchen das Muster ''anax'' im Text ''ananax''. Trifft der automatenbasierte Algorithmus bei der Suche auf das Zweite ''n'' in ''<span style="color:#008000">ana</span><span style="color:#800000">n</span>ax'', so wird er die ersten beiden Buchstaben verwerfen und beginnend mit ''an<span style="color:#008000">an</span>ax'' weitersuchen. Der naive Algorithmus hingegen hätte den kompletten bereits verarbeiteten Teil verworfen und hätte beginnend mit ''a<span style="color:#008000">n</span>anax'' einen nächsten Versuch begonnen.		Der Vorteil dieses Algorithmus gegenüber dem naiven Algorithmus liegt darin, dass er auch beim finden eines nicht-passenden Zeichens das erlangte Wissen über den bereits verarbeiteten Teil der Zeichenkette nicht verwirft. Angenommen, wir suchen das Muster ''anax'' im Text ''ananax''. Trifft der automatenbasierte Algorithmus bei der Suche auf das Zweite ''n'' in ''<span style="color:#008000">ana</span><span style="color:#800000">n</span>ax'', so wird er die ersten beiden Buchstaben verwerfen und beginnend mit ''an<span style="color:#008000">an</span>ax'' weitersuchen. Der naive Algorithmus hingegen hätte den kompletten bereits verarbeiteten Teil verworfen und hätte beginnend mit ''a<span style="color:#008000">n</span>anax'' einen nächsten Versuch begonnen.

82.149.77.122 am 1. Juli 2018 um 18:55 Uhr

2018-07-01T18:55:42Z

← Nächstältere Version		Version vom 1. Juli 2018, 20:55 Uhr
Zeile 42:		Zeile 42:
	Bei dem String-Matching-Algorithmus mit Hilfe von [[Endlicher Automat\|endlichen Automaten]] wird ein für ein Alphabet <math>\Sigma</math> und ein gegebenes Suchmuster der Länge <math>m</math> ein Automat <math>(Q, \Sigma, \delta, q_0, \{q_m\})</math> mit Zustandsmenge <math>\textstyle Q = \{q_i \mid 0 \le i \le m\}</math> erstellt. Dabei stellt <math>\textstyle i</math> die Anzahl von übereinstimmenden Buchstaben an der aktuellen Stelle vom Anfang des Suchmusters an betrachtet dar. Zur Einfachheit sei <math>\textstyle P_i</math> das [[Präfix]] des Suchmusters bis einschließlich dem Buchstaben an der Stelle <math>\textstyle i</math>. Die Übergangsfunktion <math>\delta(q_i, a)</math> mit <math>a \isin \Sigma</math> gibt nun für <math>0 \le i \le m - 1</math> wieder einen Zustand <math>q_j</math> zurück, bei dem <math>j</math> die maximale Anzahl von Buchstaben darstellt, mit der <math>P_j</math> ein [[Suffix]] vom Wort <math>P_i a</math> ist. Also <math>\delta(q_i, a) = q_{max\{j \mid P_j \text{ ist Suffix von } P_i a\}}</math>. Ist das Suchmuster gefunden, wird im Endzustand verharrt, also <math>\delta(q_m, a) = q_m</math>.		Bei dem String-Matching-Algorithmus mit Hilfe von [[Endlicher Automat\|endlichen Automaten]] wird ein für ein Alphabet <math>\Sigma</math> und ein gegebenes Suchmuster der Länge <math>m</math> ein Automat <math>(Q, \Sigma, \delta, q_0, \{q_m\})</math> mit Zustandsmenge <math>\textstyle Q = \{q_i \mid 0 \le i \le m\}</math> erstellt. Dabei stellt <math>\textstyle i</math> die Anzahl von übereinstimmenden Buchstaben an der aktuellen Stelle vom Anfang des Suchmusters an betrachtet dar. Zur Einfachheit sei <math>\textstyle P_i</math> das [[Präfix]] des Suchmusters bis einschließlich dem Buchstaben an der Stelle <math>\textstyle i</math>. Die Übergangsfunktion <math>\delta(q_i, a)</math> mit <math>a \isin \Sigma</math> gibt nun für <math>0 \le i \le m - 1</math> wieder einen Zustand <math>q_j</math> zurück, bei dem <math>j</math> die maximale Anzahl von Buchstaben darstellt, mit der <math>P_j</math> ein [[Suffix]] vom Wort <math>P_i a</math> ist. Also <math>\delta(q_i, a) = q_{max\{j \mid P_j \text{ ist Suffix von } P_i a\}}</math>. Ist das Suchmuster gefunden, wird im Endzustand verharrt, also <math>\delta(q_m, a) = q_m</math>.

	Der Vorteil dieses Algorithmus gegenüber dem naiven Algorithmus liegt darin, dass er auch beim finden eines nicht-passenden Zeichens das erlangte Wissen über den bereits verarbeiteten Teil der Zeichenkette nicht verwirft. Angenommen, wir suchen das Muster ''anax'' im Text ''ananax''. Trifft der automatenbasierte Algorithmus bei der Suche auf das Zweite ''n'' in ''<span style="color:#008000">ana</span><span style="color:#800000">n</span>ax'', so wird er die ersten beiden Buchstaben verwerfen und beginnend mit ''an<span style="color:#008000">an</span>ax''" weitersuchen. Der naive Algorithmus hingegen hätte den kompletten bereits verarbeiteten Teil verworfen und hätte beginnend mit ''a<span style="color:#~~800000~~">n</span>anax'' einen nächsten Versuch begonnen.		Der Vorteil dieses Algorithmus gegenüber dem naiven Algorithmus liegt darin, dass er auch beim finden eines nicht-passenden Zeichens das erlangte Wissen über den bereits verarbeiteten Teil der Zeichenkette nicht verwirft. Angenommen, wir suchen das Muster ''anax'' im Text ''ananax''. Trifft der automatenbasierte Algorithmus bei der Suche auf das Zweite ''n'' in ''<span style="color:#008000">ana</span><span style="color:#800000">n</span>ax'', so wird er die ersten beiden Buchstaben verwerfen und beginnend mit ''an<span style="color:#008000">an</span>ax'' weitersuchen. Der naive Algorithmus hingegen hätte den kompletten bereits verarbeiteten Teil verworfen und hätte beginnend mit ''a<span style="color:#008000">n</span>anax'' einen nächsten Versuch begonnen.

	'''Python-Implementation'''		'''Python-Implementation'''

92.77.204.64: /* Endlicher Automat */ "Präfix" ist ein Neutrum

2017-06-07T08:45:14Z

Endlicher Automat: "Präfix" ist ein Neutrum

← Nächstältere Version		Version vom 7. Juni 2017, 10:45 Uhr
Zeile 40:		Zeile 40:
	==== Endlicher Automat ====		==== Endlicher Automat ====
	[[Datei:Eines endlicher Automat zur Suche der Zeichenkette "anax" in Texten.svg\|mini\|Ein endlicher Automat zur Suche des Wortes ''anax'']]		[[Datei:Eines endlicher Automat zur Suche der Zeichenkette "anax" in Texten.svg\|mini\|Ein endlicher Automat zur Suche des Wortes ''anax'']]
	Bei dem String-Matching-Algorithmus mit Hilfe von [[Endlicher Automat\|endlichen Automaten]] wird ein für ein Alphabet <math>\Sigma</math> und ein gegebenes Suchmuster der Länge <math>m</math> ein Automat <math>(Q, \Sigma, \delta, q_0, \{q_m\})</math> mit Zustandsmenge <math>\textstyle Q = \{q_i \mid 0 \le i \le m\}</math> erstellt. Dabei stellt <math>\textstyle i</math> die Anzahl von übereinstimmenden Buchstaben an der aktuellen Stelle vom Anfang des Suchmusters an betrachtet dar. Zur Einfachheit sei <math>\textstyle P_i</math> ~~der~~ [[Präfix]] des Suchmusters bis einschließlich dem Buchstaben an der Stelle <math>\textstyle i</math>. Die Übergangsfunktion <math>\delta(q_i, a)</math> mit <math>a \isin \Sigma</math> gibt nun für <math>0 \le i \le m - 1</math> wieder einen Zustand <math>q_j</math> zurück, bei dem <math>j</math> die maximale Anzahl von Buchstaben darstellt, mit der <math>P_j</math> ein [[Suffix]] vom Wort <math>P_i a</math> ist. Also <math>\delta(q_i, a) = q_{max\{j \mid P_j \text{ ist Suffix von } P_i a\}}</math>. Ist das Suchmuster gefunden, wird im Endzustand verharrt, also <math>\delta(q_m, a) = q_m</math>.		Bei dem String-Matching-Algorithmus mit Hilfe von [[Endlicher Automat\|endlichen Automaten]] wird ein für ein Alphabet <math>\Sigma</math> und ein gegebenes Suchmuster der Länge <math>m</math> ein Automat <math>(Q, \Sigma, \delta, q_0, \{q_m\})</math> mit Zustandsmenge <math>\textstyle Q = \{q_i \mid 0 \le i \le m\}</math> erstellt. Dabei stellt <math>\textstyle i</math> die Anzahl von übereinstimmenden Buchstaben an der aktuellen Stelle vom Anfang des Suchmusters an betrachtet dar. Zur Einfachheit sei <math>\textstyle P_i</math> das [[Präfix]] des Suchmusters bis einschließlich dem Buchstaben an der Stelle <math>\textstyle i</math>. Die Übergangsfunktion <math>\delta(q_i, a)</math> mit <math>a \isin \Sigma</math> gibt nun für <math>0 \le i \le m - 1</math> wieder einen Zustand <math>q_j</math> zurück, bei dem <math>j</math> die maximale Anzahl von Buchstaben darstellt, mit der <math>P_j</math> ein [[Suffix]] vom Wort <math>P_i a</math> ist. Also <math>\delta(q_i, a) = q_{max\{j \mid P_j \text{ ist Suffix von } P_i a\}}</math>. Ist das Suchmuster gefunden, wird im Endzustand verharrt, also <math>\delta(q_m, a) = q_m</math>.

	Der Vorteil dieses Algorithmus gegenüber dem naiven Algorithmus liegt darin, dass er auch beim finden eines nicht-passenden Zeichens das erlangte Wissen über den bereits verarbeiteten Teil der Zeichenkette nicht verwirft. Angenommen, wir suchen das Muster ''anax'' im Text ''ananax''. Trifft der automatenbasierte Algorithmus bei der Suche auf das Zweite ''n'' in ''<span style="color:#008000">ana</span><span style="color:#800000">n</span>ax'', so wird er die ersten beiden Buchstaben verwerfen und beginnend mit ''an<span style="color:#008000">an</span>ax''" weitersuchen. Der naive Algorithmus hingegen hätte den kompletten bereits verarbeiteten Teil verworfen und hätte beginnend mit ''a<span style="color:#800000">n</span>anax'' einen nächsten Versuch begonnen.		Der Vorteil dieses Algorithmus gegenüber dem naiven Algorithmus liegt darin, dass er auch beim finden eines nicht-passenden Zeichens das erlangte Wissen über den bereits verarbeiteten Teil der Zeichenkette nicht verwirft. Angenommen, wir suchen das Muster ''anax'' im Text ''ananax''. Trifft der automatenbasierte Algorithmus bei der Suche auf das Zweite ''n'' in ''<span style="color:#008000">ana</span><span style="color:#800000">n</span>ax'', so wird er die ersten beiden Buchstaben verwerfen und beginnend mit ''an<span style="color:#008000">an</span>ax''" weitersuchen. Der naive Algorithmus hingegen hätte den kompletten bereits verarbeiteten Teil verworfen und hätte beginnend mit ''a<span style="color:#800000">n</span>anax'' einen nächsten Versuch begonnen.

92.77.204.64: /* Endlicher Automat */ "Suffix" ist ein Neutrum

2017-06-07T08:43:06Z

Endlicher Automat: "Suffix" ist ein Neutrum

← Nächstältere Version		Version vom 7. Juni 2017, 10:43 Uhr
Zeile 47:		Zeile 47:
	<syntaxhighlight lang="Python">		<syntaxhighlight lang="Python">
	def is_suffix(suffix, word):		def is_suffix(suffix, word):
	'''Überprüft ob ~~der~~ suffix ein Suffix von word ist.'''		'''Überprüft ob das suffix ein Suffix von word ist.'''

	return word.endswith(suffix)		return word.endswith(suffix)

Regi51: Änderungen von 87.143.156.89 (Diskussion) rückgängig gemacht (HG) (3.1.22)

2017-02-10T11:38:19Z

Änderungen von 87.143.156.89 (Diskussion) rückgängig gemacht (HG) (3.1.22)

← Nächstältere Version		Version vom 10. Februar 2017, 13:38 Uhr
Zeile 36:		Zeile 36:
	Text: aaa...aab		Text: aaa...aab
	Muster: ab		Muster: ab
	Derartige Fälle sind in natürlich sprachlichen Texten äußerst ~~Penis~~.		Derartige Fälle sind in natürlich sprachlichen Texten äußerst unwahrscheinlich.

	==== Endlicher Automat ====		==== Endlicher Automat ====
	[[Datei:Eines endlicher Automat zur Suche der Zeichenkette "anax" in Texten.svg\|mini\|Ein endlicher Automat zur Suche des Wortes ''anax'']]		[[Datei:Eines endlicher Automat zur Suche der Zeichenkette "anax" in Texten.svg\|mini\|Ein endlicher Automat zur Suche des Wortes ''anax'']]

87.143.156.89 am 10. Februar 2017 um 11:38 Uhr

2017-02-10T11:38:11Z

← Nächstältere Version		Version vom 10. Februar 2017, 13:38 Uhr
Zeile 36:		Zeile 36:
	Text: aaa...aab		Text: aaa...aab
	Muster: ab		Muster: ab
	Derartige Fälle sind in natürlich sprachlichen Texten äußerst ~~unwahrscheinlich~~.		Derartige Fälle sind in natürlich sprachlichen Texten äußerst Penis.

	==== Endlicher Automat ====		==== Endlicher Automat ====
	[[Datei:Eines endlicher Automat zur Suche der Zeichenkette "anax" in Texten.svg\|mini\|Ein endlicher Automat zur Suche des Wortes ''anax'']]		[[Datei:Eines endlicher Automat zur Suche der Zeichenkette "anax" in Texten.svg\|mini\|Ein endlicher Automat zur Suche des Wortes ''anax'']]

109.46.252.29: /* Multi-String-Matching */

2016-11-18T23:50:13Z

Multi-String-Matching

← Nächstältere Version		Version vom 19. November 2016, 01:50 Uhr
Zeile 150:		Zeile 150:
	== Multi-String-Matching ==		== Multi-String-Matching ==

	Die Suche nach mehreren Mustern in einem Text nennt sich Multi-String-Matching<ref>{{Literatur \|Autor=Gonzalo Navarro, Mathieu Raffinot \|Titel=Flexible Pattern Matching Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences \|Datum=2008 \|ISBN=0-521-03993-2}}</ref>. Die meisten Algorithmen sind abgeleitet von einem entsprechenden String-Matching Algorithmus für ~~ganau~~ ein Muster. Eine besondere Herausforderung bei der Suche nach mehreren Suchwörtern ist die Behandlungen von Wort-Überlappungen.		Die Suche nach mehreren Mustern in einem Text nennt sich Multi-String-Matching<ref>{{Literatur \|Autor=Gonzalo Navarro, Mathieu Raffinot \|Titel=Flexible Pattern Matching Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences \|Datum=2008 \|ISBN=0-521-03993-2}}</ref>. Die meisten Algorithmen sind abgeleitet von einem entsprechenden String-Matching Algorithmus für genau ein Muster. Eine besondere Herausforderung bei der Suche nach mehreren Suchwörtern ist die Behandlungen von Wort-Überlappungen.

	=== Liste von Algorithmen ===		=== Liste von Algorithmen ===