[QUIZ#1] Matthias Reitinger (C++)


#1
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:
#3
Aber bitte nicht so! Das mit !eof() funktioniert nicht zuverlässig. Du kannst nicht davon ausgehen, das das geline() nach dem !eof() Check auch wirklich etwas einliest.

Warum nicht einfacher?
C++:
while (getline(is, haystack)) {
  match(needle, haystack);
}
Stimmt natürlich. Danke für den Hinweis! Hab irgendwie doch schon länger nichts mehr in C++ gemacht.

Grüße,
Matthias
 

deepthroat

Erfahrenes Mitglied
#5
Hi.

Ich denke ich habe noch eine schöne Lösung gefunden. Dabei hab ich mal die std::mismatch Funktion eingesetzt:
C++:
bool
fuzzy_match(const string& needle, const string& haystack, string& result) {
  typedef string::const_iterator iter_t;

  if (needle.empty()) { result = haystack; return true; }

  result.clear();

  iter_t n_beg = needle.begin(),   n_end = needle.end();
  iter_t h_beg = haystack.begin(), h_end = haystack.end();

  while (h_beg != h_end) {
    iter_t start = find(h_beg, h_end, *n_beg);

    copy(h_beg, start, back_inserter(result));
    
    if (start == h_end || distance(start, h_end) < distance(n_beg, n_end)) break;

    pair<iter_t, iter_t> stop = mismatch(start + 1, h_end, n_beg + 1);

    result += '<';
    copy(start, stop.first, back_inserter(result));
    result += '>';

    h_beg = stop.first;
    n_beg = stop.second;
  }
  return (n_beg == n_end);
}
Gruß
 
Zuletzt bearbeitet:

Neue Beiträge