[QUIZ#1] Unscharfe Suche

Quiz #1
Unscharfe Suche

Regeln
Die Regeln und der Ablauf der Quizrunde können wie immer in der entsprechenden Ankündigung eingesehen werden. Bitte lest sie euch aufmerksam durch, da sie alle wichtigen Informationen enthält.

Abgabe
Die Abgabe erfolgt wie immer im Abgabeforum. Abgabefrist ist Sonntag, der 21. September 2008 um ca. 20 Uhr.

Das Problem
Der Suchmaschinenbetreiber Hupf entwickelt zur Zeit einen neuen Browser namens "Titan". Als "Killerfeature" soll der Benutzer mit der browserinternen Suchfunktion auch eine sogenannte unscharfe Suche durchführen können. Deine Aufgabe besteht nun darin, einen entsprechenden Algorithmus für einen Prototypen des Browsers zu implementieren.

Die Unschärfe entsteht dadurch, dass es keine exakte Übereinstimmung geben muss, sondern nur alle Zeichen des Suchbegriffes in der gegebenen Reihenfolge in der Zeichenfolge vorkommen müssen. Als Beispieldatensatz steht eine Liste US-amerikanischer Präsidenten zur Verfügung. Das Programm soll diese Liste einlesen und alle Einträge ausgeben, die durch eine unscharfe Suche nach dem als Kommandozeilenparameter übergebenen Begriff gefunden werden.

Erweiterung
Als zusätzliches Feature sollen in der Ausgabe die übereinstimmenden Teile markiert werden (siehe Beispiele). Die Implementierung dieser Erweiterung ist euch freigestellt.

Beispiele
Eingabe:
Code:
George Bush
Erwartete Ausgabe (einfach):
Code:
George H. Bush
George W. Bush
Erwartete Ausgabe (erweitert):
Code:
<George> H. <Bush>
<George> W. <Bush>

Eingabe:
Code:
JFK
Erwartete Ausgabe (einfach):
Code:
John F. Kennedy
Erwartete Ausgabe (erweitert):
Code:
<J>ohn <F>. <K>ennedy

Eingabe:
Code:
oooo
Erwartete Ausgabe (einfach):
Code:
Theodore Roosevelt
Woodrow Wilson
Erwartete Ausgabe (erweitert):
Code:
The<o>d<o>re R<oo>sevelt
W<oo>dr<o>w Wils<o>n


Vielen Dank an Gumbo für die Einsendung dieser Aufgabe!
 

Anhänge

  • presidents.txt
    655 Bytes · Aufrufe: 230
Zuletzt bearbeitet:
Die Suche nach oooo sollte auch noch Woodrow Wilson ausspucken.
Vielen Dank für den Hinweis, ich habe das Beispiel entsprechend angepasst.

Grover Cleveland steht 2 mal in der Liste, wundert euch also nicht falls dieser Name doppelt in euren Ergebnissen auftaucht :)
Ja, stimmt, sollte aber auch nicht stören :)

Heißt soviel wie muss nicht implementiert sein?
Genau. Wenn dir die Erweiterung zu kompliziert ist, musst du sie nicht implementieren. Was natürlich nicht heißt, dass man es nicht trotzdem probieren sollte :)
 

Nils Hitze

Admin a.D.
Wuild, sehr schöne Aufgabe die ihr das rausgesucht habt, da bin ich ja fast versucht, wenn ich nicht soviel zu tun hätte .. mal gucken. Bin jedenfalls gespannt wie das Ergebniss der Übung aussieht.