Längste Sequenz aus gleichen Buchstaben?



  • Hallo,

    ich versuche mich gerade an einem Algorithmus der mir die längste Sequenz an gleichen, aufeinanderfolgenden chars aus einem std::string zurückgibt. Beispiel:

    std::string s = "axxabbxxxcdk123xxxxfgxx";
    //                              ^^^^
    

    Oben markiert wäre das Ergebnis, das ich am liebsten als Iterator Paar haben wollen würde (oder Position + Länge). Der Such-Buchstabe (hier x) soll auch als Parameter übergeben werden.

    Ich hab mich mit std::adjacent_find daran versucht, aber dieses gibt ja immer nur einen iterator auf den Beginn der Sequenz zurück, nicht wie lange diese ist (und ich brauche ja die längste).

    Gibts da was passenderes als std::adjacent_find oder wie würde man das am besten machen?



  • Das kommt raus, wenn man immer lehrt, stl-Algos statt eigener Schleifen zu verwenden.



  • Wie wärs denn mit sowas hier?
    Ist nur mäßig umständlich und sollte für alle nicht-leeren Strings die längste Sequenz bestimmen (Iteratoren a und b ).
    Bei mehreren gleich langen längsten Sequenzen wird die erste zurückgegeben.
    Bei einem leeren String ist cbegin == cend , weshalb i nicht inkrementierbar ist (muss man vorher prüfen).

    std::string s = "axxabbxxxcdk123xxxxfgxx";
        auto i = std::cbegin(s), a = i, b = i, start = i;
    
        do
        {
            ++i;
            if (i == std::cend(s) || *i != *start)
            {
                if (i - start > b - a)
                {
                    a = start;
                    b = i;
                }
                start = i;
            }
        }
        while (i != std::cend(s));
    
        std::cout << s << std::endl;
        std::cout << std::string(a - std::cbegin(s), ' ') << std::string(b - a, '^') << std::endl;
    

    Gruss,
    Finnegan


  • Mod

    Mein Vorschlag:

    #include <algorithm>
    #include <iterator>
    #include <type_traits>
    
    template <typename InputIt, typename Comparator>
    InputIt adjacent_find_end(InputIt first, InputIt last, Comparator comp) {
    	auto i = std::adjacent_find(first, last, [&] (auto const&... a) {return !comp(a...);});
    	return i == last? last : ++i;
    }
    template <typename BiDirIt, typename Comparator>
    BiDirIt adjacent_find_first(BiDirIt first, BiDirIt last, Comparator comp) {
    	return adjacent_find_end(std::make_reverse_iterator(++last), std::make_reverse_iterator(first), comp).base();
    }
    
    template <typename RandomIt, typename Comparator>
    std::pair<RandomIt, RandomIt> longest_adjacent( RandomIt first, RandomIt last, Comparator comp ) {
    	if (first == last)
    		return {first, last};
    	typename std::iterator_traits<RandomIt>::difference_type len = 1;
    	auto best = first;
    	first += len;
    	while (last-first > len) {
    		first += len;
    		auto begin = adjacent_find_first(first-len, first, comp), end = first+1;
    		if (end != last)
    			end = adjacent_find_end(end, last, comp);
    		if (end-begin > len) {
    			best = begin;
    			len = end-begin;
    		}
    		first = end;
    	}
    
    	return {best, best+len};
    }
    
    template <typename RandomIt>
    std::pair<RandomIt, RandomIt> longest_adjacent( RandomIt first, RandomIt last ) {
    	return longest_adjacent(first, last, std::equal_to<>{});
    }
    
    /// Test:
    #include <iostream>
    
    int main() {
    	int arr[] = {0, 0, 1, 1, 1,   2, 3, 5, 5, 5,   5, 0, 0, 0, 0,   6, 6, 6, 6, 6 };
    	std::cout << longest_adjacent(std::begin(arr), std::end(arr), std::equal_to<>{}).first-arr;
    }
    

    Edit: Sorry, was hab' ich denn da geschrieben..
    Edit²: Vereinfacht.



  • Arcoth schrieb:

    Mein Vorschlag:

    #include <algorithm>
    #include <iterator>
    #include <type_traits>
    
    template <typename InputIt, typename Comparator>
    InputIt adjacent_find_end(InputIt first, InputIt last, Comparator comp) {
    	auto i = std::adjacent_find(first, last, [&] (auto const&... a) {return !comp(a...);});
    	return i == last? last : ++i;
    }
    template <typename BiDirIt, typename Comparator>
    BiDirIt adjacent_find_first(BiDirIt first, BiDirIt last, Comparator comp) {
    	return adjacent_find_end(std::make_reverse_iterator(++last), std::make_reverse_iterator(first), comp).base();
    }
    
    template <typename RandomIt, typename Comparator>
    std::pair<RandomIt, RandomIt> longest_adjacent( RandomIt first, RandomIt last, Comparator comp ) {
    	if (first == last)
    		return {first, last};
    	typename std::iterator_traits<RandomIt>::difference_type len = 1;
    	auto best = first;
    	first += len;
    	while (last-first > len) {
    		first += len;
    		auto begin = adjacent_find_first(first-len, first, comp), end = first+1;
    		if (end != last)
    			end = adjacent_find_end(end, last, comp);
    		if (end-begin > len) {
    			best = begin;
    			len = end-begin;
    		}
    		first = end;
    	}
    
    	return {best, best+len};
    }
    
    template <typename RandomIt>
    std::pair<RandomIt, RandomIt> longest_adjacent( RandomIt first, RandomIt last ) {
    	return longest_adjacent(first, last, std::equal_to<>{});
    }
    
    /// Test:
    #include <iostream>
    
    int main() {
    	int arr[] = {0, 0, 1, 1, 1,   2, 3, 5, 5, 5,   5, 0, 0, 0, 0,   6, 6, 6, 6, 6 };
    	std::cout << longest_adjacent(std::begin(arr), std::end(arr), std::equal_to<>{}).first-arr;
    }
    

    Edit²: Vereinfacht.

    👍 🤡
    Jetzt fehlt noch, die Funktionalität in einen streambuf zu packen.



  • Wenn man nur die Anzahl und den Wert des Elementes liefert, käme man mit einem Forward Iterator aus. Dann könnte man auch einen std::streambuf_iterator verwenden. Als Rückgabe einen std::streambuf_iterator würde so wirklich gar keinen Sinn machen.



  • Wenn man O(N) akzeptiert kommt man sowieso mit einem Forward-Iterator aus 😕

    Kann's sein dass du volkard's Scherz nicht verstanden hast?
    EDIT: Kann's sein dass ich deinen Scherz nicht verstanden hab? (Vermutlich. Versteh' ihn aber immer noch nicht.)



  • Sowas ist einfach zu schwer zu programmieren. Aber vielleicht hat die NASA einen Webservice den man ansprechen kann?!



  • Vielen Dank für die Vorschläge 👍


Anmelden zum Antworten