[Hilfe] Suchen nach 10stelliger zahl in Text

[otze]

seldon schrieb:

Um auf das Problem des TE zurückzukommen, es gibt eine ganze Reihe von Algorithmen, die deutlich schneller als die Brechstangenmethode laufen. Der bekannteste ist vermutlich der Boyer-Moore-Algorithmus oder die Vereinfachung durch Horspool. Diese sind aber natürlich komplexer zu implementieren.

Wie bereits gesagt, musst du in einem binären Alphabet bei einem Muster wie "1111111111" exakt n vergleiche machen, wenn du alle Vorkommen des Musters in einem String mit Länge n finden willst. Im Grunde geht es darum nicht besser als der Algorithmus, den ich auf Seite 1 genannt habe(*). Allerdings kann man sich sicher noch um eine schöne Darstellung kümmern.

(*) mal davon abgesehen, dass man sich eventuell die letzten 9 Vergleiche sparen kann. Ich würde aber schätzen, dass diese Bedingung bei einem langen string wesentlich mehr Zeit kosten würde, als die 9 Vergleiche wirklich durchzuführen

//edit
Pi, geh auf der Autobahn mit 133 Autos spielen. (nein, ich hab kein Niveau um das ich mir sorgen machen müsste)

[314159265358979]

otze schrieb:

Pi, geh auf der Autobahn mit 133 Autos spielen. (nein, ich hab kein Niveau um das ich mir sorgen machen müsste)

Stimmt, du postest hier ja sowieso außer Konkurrenz.

[Gast]

314159265358979 schrieb:

hustbaer, ich liebe dich. Lass uns heiraten, okay?

Klar, Santa. Ich mag Sellerie auch nicht.

[hustbaer]

314159265358979 schrieb:

P.S.: Jemandem den Tod zu wünschen, ist unter deinem Niveau.

Ach, das ist aber schön dass du mich für niveauvoll hältst.

Lass dir mal neue Arten der indirekten Beleidigung einfallen.
"unter deinem Niveau", "von dir hätte ich mir mehr erwartet" etc. - das wird langsam alt.

Im Übrigen kann ich das Kompliment nicht zurückgeben. Ich denke dass Threads wie dieser hier ganz genau dein Niveau widerspiegeln.

[314159265358979]

Ne, Threads wie diese spiegeln meine Stimmung wieder. Im übrigen ist mir gerade danach, aus dem Fenster zu springen, also lutsch meine Eier, leck' mich am Arsch, etc. etc.

[pyhax]

Ist hier ein Mod der diesen Thread schließen könnte?

[beweis]

Dem Forum fehlen einfach die coolen Coder, nur noch Dummschwätzer da.

[Gast]

pyhax schrieb:

Ist hier ein Mod der diesen Thread schließen könnte?

[C++Guid]

fghfgh schrieb:

#include <iostream>
#include <string>

std::string getNumber(const std::string& str, std::size_t len);

int main()
{
	std::string str = "009asbdfap91234usdfha9sdfuasdfa9shf9876503864a98sdbf98abdasd";

	std::cout << getNumber(str, 10);
}

std::string getNumber(const std::string& str, std::size_t len)
{
	std::size_t newPos = 0, nextPos = 0;

	for (;(newPos = str.find_first_of("0123456789", newPos)) != std::string::npos && (nextPos = str.find_first_not_of("0123456789", newPos)) - newPos != len && nextPos != std::string::npos;++newPos);

	if (newPos != std::string::npos && nextPos != std::string::npos)
		return str.substr(newPos, nextPos - newPos);

	return "";
}

Eine spontane Idee. :xmas1:

genau sowas suche ich danke jetzt noch eine kleine frage was ist wenn ich gleichzeitig wieder selbe Problem nur jetzt 10 und 11 stellige zahlen codes... wo gib ich das am besten an?

MFG

[otze]

Zum Beispiel dort, wo jetzt die 10 steht?

[Gast]

Das dürfte aus dem Kontext her ersichtlich sein. Ich schlage (gegen deine willkürliche Intuition) vor, dir den Code einmal selbst anzuschauen und mal zu sehen, was er bedeutet. Da gibt es ein Variäbelchen 'len', das dürfte vielversprechend sein.

[Gast]

otze schrieb:

Zum Beispiel dort, wo jetzt die 10 steht?

Genau, otze. Einfach alle 10er durch 11er ersetzen, dann klappts

[C++Guid]

ja is klar ich hab mir auch den code angeschaut so is es ja nicht nur geht meine Idee nicht so wirklich siehe..

#include <iostream>
#include <string>

std::string getNumber(const std::string& str, std::size_t len, std::size_t len2);

int main()
{
    std::string str = "009asbdfap91234usdfha9sdfuasdfa9shf9876503864a98sdbf98abdasd";

    std::cout << getNumber(str, 10, 11);
}

std::string getNumber(const std::string& str, std::size_t len, std::size_t len2)
{
    std::size_t newPos = 0, nextPos = 0;

    for (;(newPos = str.find_first_of("0123456789", newPos)) != std::string::npos && (nextPos = str.find_first_not_of("0123456789", newPos)) - newPos != len && newPos != len2 && nextPos != std::string::npos;++newPos);

    if (newPos != std::string::npos && nextPos != std::string::npos)
        return str.substr(newPos, nextPos - newPos);

    return "";
}

[fghfgh]

Ich hab die Funktion noch etwas angepasst, da sie in einigen Situationen nicht korrekt funktioniert hat.

Hier das Ergebnis:

#include <iostream>
#include <string>

std::string getNumber(const std::string& str, std::size_t len);

int main()
{
    std::string str = "002asbdfap91234usdfha9sdfuasdfa9shf9876503864x123123x9218391283981239812x129381289381290312xasd0123311";

	for (int i = 0; i <= 30; ++i)
	{
		std::cout << i << " => " << getNumber(str, i) << std::endl;
	}
}

std::string getNumber(const std::string& str, std::size_t len)
{
    std::size_t newPos = 0, nextPos = 0;
	for (;(newPos = str.find_first_of("0123456789", newPos)) != std::string::npos && ((nextPos = (str + "#").find_first_not_of("0123456789", newPos)) - newPos != len); newPos += 1 + (nextPos != std::string::npos ? nextPos - newPos : 0));

    if (newPos != std::string::npos && nextPos != std::string::npos)
        return str.substr(newPos, nextPos - newPos);

    return "";
}

Die Funktion wird einfach mehrmals aufgerufen, um Zahlen verschiedener Länge zu extrahieren. Das scheint auch alles perfekt zu klappen, aber durch die Verbesserungen wird die Funktion so langsam unübersichtlich.

[westerwello]

fghfgh schrieb:

durch die Verbesserungen wird die Funktion so langsam unübersichtlich.

Darum:

#include <iostream>
#include <algorithm>
#include <string>

std::string getNumber(const std::string& str, std::size_t len);

int main()
{
  std::string str = "002asbdfap91234usdfha9sdfuasdfa9shf9876503864x123123x9218391283981239812x129381289381290312xasd0123311";

  for (int i = 0; i <= 30; ++i) {
    std::cout << i << " => " << getNumber(str, i) << std::endl;
  }
}

bool first_is_digit(char c, char) { return std::isdigit(c); }

std::string getNumber(const std::string& str, std::size_t len)
{
  std::string::const_iterator pos = std::search_n(str.begin(), str.end(), len, '\0', first_is_digit);
  if (pos == str.end())
    return "";
  return std::string(pos, pos + len); 
}

[fghfgh]

westerwello schrieb:

fghfgh schrieb:

durch die Verbesserungen wird die Funktion so langsam unübersichtlich.

Darum:

#include <iostream>
#include <algorithm>
#include <string>

std::string getNumber(const std::string& str, std::size_t len);

int main()
{
  std::string str = "002asbdfap91234usdfha9sdfuasdfa9shf9876503864x123123x9218391283981239812x129381289381290312xasd0123311";

  for (int i = 0; i <= 30; ++i) {
    std::cout << i << " => " << getNumber(str, i) << std::endl;
  }
}

bool first_is_digit(char c, char) { return std::isdigit(c); }

std::string getNumber(const std::string& str, std::size_t len)
{
  std::string::const_iterator pos = std::search_n(str.begin(), str.end(), len, '\0', first_is_digit);
  if (pos == str.end())
    return "";
  return std::string(pos, pos + len); 
}

Grundsätzlich:

Aber, Ausgabe:

0 =>
1 => 0
2 => 00
3 => 002
4 => 9123
5 => 91234
6 => 987650
7 => 9876503
8 => 98765038
9 => 987650386
10 => 9876503864
11 => 92183912839
12 => 921839128398
13 => 9218391283981
14 => 92183912839812
15 => 921839128398123
16 => 9218391283981239
17 => 92183912839812398
18 => 921839128398123981
19 => 9218391283981239812
20 =>
21 =>
22 =>
23 =>
24 =>
25 =>
26 =>
27 =>
28 =>
29 =>
30 =>

vs.

0 =>
1 => 9
2 =>
3 => 002
4 =>
5 => 91234
6 => 123123
7 => 0123311
8 =>
9 =>
10 => 9876503864
11 =>
12 =>
13 =>
14 =>
15 =>
16 =>
17 =>
18 => 129381289381290312
19 => 9218391283981239812
20 =>
21 =>
22 =>
23 =>
24 =>
25 =>
26 =>
27 =>
28 =>
29 =>
30 =>

[seldon]

Grammarnazi schrieb:

seldon schrieb:

der Boyer-Moore-Algorithmus oder die Vereinfachung durch Horspool.

Wenn schon, dann KMP. Den hat man übrigens, wenn man den GCC und strstr verwendet.

In diesem Fall brauchts aber gar kein Backtracking, da es nur Zahl oder Nichtzahl gibt.

Das ist so nicht korrekt. Aus den glibc-Sourcen, string/str-two-way.h (diese wird in strstr verwendet):

/* We use the Two-Way string matching algorithm, which guarantees
   linear complexity with constant space.  Additionally, for long
   needles, we also use a bad character shift table similar to the
   Boyer-Moore algorithm to achieve improved (potentially sub-linear)
   performance.

   See http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260
   and http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm
*/

Generell ist Boyer-Moore KMP in der Regel laufzeittechnisch überlegen (nicht immer aber Boyer-Moore-Horspool!), wenn es nicht gerade um so kurze Textstücke geht, dass der Aufbau der Tabellen für Boyer-Moore ins Gewicht schlägt - daher wird die glibc ihn für strstr auch nicht verwenden, denn da dürfte das häufig der Fall sein.

Es gibt da einen interessanten Beitrag auf der FreeBSD-Mailingliste vom ursprünglichen Entwickler von GNU Grep, der diese Dinge (mit Bonusfokus auf Dateiverarbeitung) nähere erläutert. Ferner gibt es übrigens eine weitere Verbesserung, die sich (vielleicht etwas prätentiös) Turbo-Boyer-Moore nennt und vom worst-case noch mal ein Drittel absäbelt.

Wie dem auch sei, ich muss mich insofern entschuldigen, als dass das alles auf die ursprüngliche Aufgabe nur begrenzt passt - ich hatte das so gelesen, dass eine bestimmte zehnstellige Zahl gesucht wird. Allerdings kann man einige der Ideen trotzdem verwenden; praktisch kann man den String als Zeichenkette über ein Alphabet der Größe zwei (Ziffer/Nichtziffer) verstehen. Tabellen aufzustellen lohnt sich dann nicht, aber rumspringen kann man trotzdem, um die Vergleichszahl zu drücken. Ich stelle mir das etwa so vor (jetzt mal einfach hingekladdet):

#include <algorithm>
#include <cctype>
#include <iostream>
#include <iterator>
#include <string>

int const N = 10;

int ccount = 0;

bool is_digit(char c) {
  ++ccount;
  return std::isdigit(c);
}

int main() {
  std::string str = "002asbdfap91234usdfha9sdfuasdfa9shf9876503864x123123x9218391283981239812x129381289381290312xasd0123311";

  int i, j, k;

  for(k = i = N - 1; i < str.size(); k = i = k + N) {
    if(is_digit(str[i])) {
      for(j = i - 1; j > i - N && is_digit(str[j]); --j)
        ;

      if(j + N < str.size()) {
        for(k = j + N; k != i && is_digit(str[k]); --k)
          ;

        if(k == i) {
          std::copy(str.begin()     + 1 + j,
                    str.begin() + N + 1 + j,
                    std::ostream_iterator<char>(std::cout, ""));
          std::cout << std::endl;
          break;
        }
      }
    }
  }

  std::cout << ccount << " Vergleiche wurden benötigt." <<  std::endl;
}

[seldon]

Ich hab noch mal in Ruhe drüber nachgedacht, und da lässt sich noch was drehen. Man kann die doppelte Prüfung einzelner Zeichen vermeiden, indem man sich bereits geprüfte Bereiche merkt, und man kann große Teile überspringen, indem man sich zunutze macht, dass das Ende eines Strings von 10 Ziffern keinesfalls in den neun Zeichen hinter einer Nicht-Ziffer liegen kann.

Auf die Art kann ich bei einem Eingabestring der Länge n garantieren, dass ncith mehr als n Vergleiche benutzt werden - worst-case ist ein String der Form

std::string str = 
    "x012345678"
    "xx012345678"
    "xx012345678"
    "xx012345678"
    "xx1234567890";

Im besten Fall befindet sich die Vergleichszahl bei etwa p / 10 + 10, wobei p die Position der gesuchten Nadel im Heuhaufen ist, weil in Blöcken von bis zu zehn Zeichen übersprungen werden kann.

Der Algorithmus sieht dann so aus:

#include <algorithm>
#include <cctype>
#include <iostream>
#include <iterator>
#include <string>

int const N = 10;

class counting_digit_predicate {
public:
  counting_digit_predicate() : ccount_(0) { }

  bool operator()(char c) {
    ++ccount_;
    return std::isdigit(c) != 0;
  }

  int counter() const { return ccount_; }

private:
  int ccount_;
};

int main() {
  std::string str = "002asbdfap91234usdfha9sdfuasdfa9shf9876503864x123123x9218391283981239812x129381289381290312xasd0123311";

  counting_digit_predicate is_digit;
  int i, j, k, l;

  for(i = N - 1, k = l = -1; i < str.size(); i = k + N) {
    if(!is_digit(str[i])) {
      k = i;
      continue;
    }

    for(j     = i - 1; j > l && is_digit(str[j]); --j) ;
    if(j == l) j = k;
    for(k = l = j + N; k > i && is_digit(str[k]); --k) ;

    if(k == i) {
      std::copy(str.begin()     + 1 + j,
		str.begin() + N + 1 + j,
		std::ostream_iterator<char>(std::cout, ""));
      std::cout << std::endl;
      break;
    }
  }

  std::cout << is_digit.counter() << " Vergleiche wurden benötigt." <<  std::endl;
}

...ein vernünftiges Interface drumherumzuschustern, sie dem Leser als Übungsaufgabe überlassen.

[Patrickssj6]

Wenn der Text lang genug ist, lohnt sich eine Vorverarbeitung. Danach kann man in garantierter linearer Zeit alles finden.

[Ethon]

Falls es immer noch um das Problem geht, sollte so funktionieren (ungetestet):

#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>

int main()
{
    std::string str("002asbdfap91234usdfha9sdfuasdfa9");
    auto iter = std::search_n(str.begin(), str.end(), 9, char(), [](char, char cur) { return std::isdigit(cur); });
    iter == str.end() ? std::cout << "No match" : std::cout << "Match at " << iter - str.begin();
}