Matthias Reitinger
ɐɯıǝɹ
C++:
#include <fstream>
#include <string>
#include <iterator>
#include <iostream>
#include <list>
using namespace std;
typedef pair<size_t, size_t> range;
void match(const string& needle, const string& haystack) {
size_t offset = -1; // Aktuelle Position in haystack
list<range> ranges; // Liste aller übereinstimmenden Bereiche
string::const_iterator it = needle.begin();
for (; it != needle.end(); it++) {
// Ignoriere Leerzeichen
if (isspace(*it))
continue;
// Finde nächste Übereinstimmung, falls vorhanden
offset = haystack.find(*it, offset + 1);
// Keine Übereinstimmung gefunden?
if (offset == string::npos)
return;
if (ranges.empty() || ranges.front().second != offset) {
// Erstelle neuen Bereich, da der letzte Bereich nicht mit dieser
// Übereinstimmung zusammenhängt. push_front wird verwendet, weil
// wir die Bereiche später beim Markieren von hinten nach vorne
// durchlaufen wollen.
ranges.push_front(make_pair(offset, offset + 1));
} else {
// Letzte Übereinstimmung lag unmittelbar vor dieser, erweitere Bereich
ranges.front().second++;
}
}
// Suche erfolgreich, markiere Bereiche und gebe aus
string result(haystack);
list<range>::iterator rit = ranges.begin();
for (; rit != ranges.end(); rit++) {
result.insert(rit->second, ">");
result.insert(rit->first, "<");
}
cout << result << endl;
}
int main(int argc, char** argv) {
if (argc < 2) {
cout << "missing argument" << endl;
return 0;
}
ifstream is("presidents.txt");
string haystack;
string needle(argv[1]);
while (!is.eof()) {
getline(is, haystack);
match(needle, haystack);
}
return 0;
}
Der Algorithmus durchläuft die einzelnen Zeichen der Suchanfrage und springt dabei im zu durchsuchenden String von Fundstelle zu Fundstelle. Nebenbei wird eine Liste von zusammenhängenden Bereichen erstellt, die später für die Hervorhebung verwendet wird. Auch als Ruby-Variante erhältlich.
Zuletzt bearbeitet: