[Hilfe] Suchen nach 10stelliger zahl in Text
-
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(); }
-
C++Guid schrieb:
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
Hallo
Ich hab bezüglich des Codes nur eine kleine Frage:
Ist es nicht so, dass schlussendlich die Funktionen find_first_of und find_first_not_of im Hintergrund ähnlich den String durchlaufen wie von der Anfangsidee des TE und damit vom Rechenaufwand ähnlich wäre? Oder irre ich mich bei diesem Gedanken?Vielen Dank!
Gruss,
Vfrg
-
find_first_of und find_first_not_of sind Funktionen, die aus einer Zeichenkette einfach jedes Zeichen berücksichtigen, anstatt wie bei find nur eines.
-
Vfrg schrieb:
C++Guid schrieb:
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
Hallo
Ich hab bezüglich des Codes nur eine kleine Frage:
Ist es nicht so, dass schlussendlich die Funktionen find_first_of und find_first_not_of im Hintergrund ähnlich den String durchlaufen wie von der Anfangsidee des TE und damit vom Rechenaufwand ähnlich wäre? Oder irre ich mich bei diesem Gedanken?Vielen Dank!
Gruss,
VfrgJa, damit hast du recht. Allerdings kann es natürlich sein, dass diese Funktionen optimierter sind, als hätte man es von Hand geschrieben. Im einfachsten Fall läuft es aber auf das gleiche hinaus.
-
Ja, damit hast du recht. Allerdings kann es natürlich sein, dass diese Funktionen optimierter sind, als hätte man es von Hand geschrieben. Im einfachsten Fall läuft es aber auf das gleiche hinaus.
Danke für die Erklärung!
Gruss,
Vfrg
-
Ich hatte den Thread schon vor drei Tagen mit Interesse verfolgt, aber bisher keine Gelegenheit darauf zu antworten. Dass std::search_n das Mittel der Wahl ist, wurde bereits erwähnt. Und natürlich benutzen die Implementierungen ähnliche Strategien wie den 'Boyer-Moore-Algorithmus'.
Wichtig zu wissen ist aber noch, dass die Implementierung im Visual Studio 2005 buggy ist!
Ich habe mal einen kleinen Iteratorwrapper gebastelt um deutlich zu machen, was da passiert. Im 2008'er und jüngeren Versionen ist das Problem behoben.#include <iostream> #include <string> #include <cassert> #include <algorithm> // std::search_n #include <locale> #include <iomanip> // std:.setw #include <boost/iterator/iterator_adaptor.hpp> template< typename Base > class AccessViewer : public boost::iterator_adaptor< AccessViewer< Base >, Base > { public: AccessViewer() : iterator_adaptor_() , m_idx() {} AccessViewer( Base cur, Base begin ) : iterator_adaptor_( cur ) , m_idx( std::distance( begin, cur ) ) {} void increment() { ++m_idx; ++base_reference(); } void decrement() { --m_idx; --base_reference(); } void advance( typename Base::difference_type n ) { m_idx += n; std::advance( base_reference(), n ); } typename Base::reference dereference() const { std::clog << std::setw( std::streamsize( m_idx + 1 ) ) << "^" << std::endl; return *base(); } private: typename Base::difference_type m_idx; }; template< typename Base > AccessViewer< Base > access_viewer( Base cur, Base begin ) { return AccessViewer< Base >( cur, begin ); } int main() { using namespace std; string txt = "009asbdfap9usdfha9sdfuasdfa9shf9876503864a98sdbf98abdasd"; for( int n = 2; n < 15; n == 2? n = 10: n == 10? n = 12: n = 99 ) { clog << "\n" << txt << endl; string::iterator found = std::search_n( access_viewer( txt.begin(), txt.begin() ), access_viewer( txt.end(), txt.begin() ), n, locale(), &std::isdigit<char> ).base(); cout << n << " digits: " << txt.substr( distance( txt.begin(), found ), min( distance( found, txt.end() ), n ) )<< endl; } return 0; }Die Ausgabe sieht im Gutfall so aus (mit VS 2008 Express):
009asbdfap9usdfha9sdfuasdfa9shf9876503864a98sdbf98abdasd ^ ^ 2 digits: 00 009asbdfap9usdfha9sdfuasdfa9shf9876503864a98sdbf98abdasd ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ 10 digits: 9876503864 009asbdfap9usdfha9sdfuasdfa9shf9876503864a98sdbf98abdasd ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ 12 digits:Bei jedem Zugriff auf ein Element durch den Algorithmus wird eine Zeile ausgegeben. Der 'Pfeil nach oben' zeigt jeweils an an welcher Stelle gerade zugegriffen wird. Man sieht sehr schön, wie der Algorithmus zwar vorn anfängt, dann aber in n'er Schritten weiter sucht, den Anfang der Ziffernkette sucht, um anschließend den Rest der n Zeichen zu prüfen.
Es fällt noch auf, dass am Anfang immer ein Zeichen mehr geprüft wird als notwendig.Wer noch über ein Visual Studio 2005 verfügt, möge es da mal mit probieren.
Gruß
Werner
-
Hallo,
Werner's Boyer Moore dürfte neben heuristischen Methoden (die nur möglich sind, wenn man etwas mehr über den string weiß) die schnellste sein, mit einer Änderung: man fängt beim 10. char an, nicht beim Ersten!
Immer 10 springen und rückwärtssuchen.
Nach dem Sprung kann man in sofern noch abkürzen, wenn man im vorherigen rückwärtssuchen n gefunden hat braucht man bei folgenden rückwärtssuchen nur noch 10-n finden.Ich denke, dass search_n mit Boyer Moore arbeitet, aber der Fakt dass alles zahlen sind, nicht berücksichtigen kann. Es wird eine Gruppe aus Zahlen gesucht, nicht ein string im string. Somit ist das gleichzustellen mit alle Buchstaben werden zu "b" und alle Zahlen werden zu "z" und es muss nach "zzzzzzzzzz" gesucht werden. Jetzt wenn man den Boyer Moore anwendet merkt man schnell, dass manche Vergleiche zu viel sind:
v v zzzzbbzbzbzbzzzzzbzzzzzzzzzzbzbzbzzzzb zzzzzzzzz[u]z[/u] zzzzzzzzz[u]z[/u] zzzzzzzz[u]z[/u]z zzzzzzz[u]z[/u]zz zzzzzzzzz[u]z[/u] zzzzzzzz[u]z[/u]z zzzzzzz[u]z[/u]zz zzzzzz[u]z[/u]zzz zzzzz[u]z[/u]zzzz zzzz[u]z[/u]zzzzz zzz[u]z[/u]zzzzzz zz[u]z[/u]zzzzzzz // Hier endet ein schlauer Algorithmus, denn es wurden bereits 2x "z" gefunden z[u]z[/u]zzzzzzzz [u]z[/u]zzzzzzzzz // Hier endet erst der Bayor MooreViel Spass damit, ich hoffe ich keine Denkfehler habe!
gruß Philipp