Looking for repeating patterns in integer numbers

Question

I am trying to find repeating patterns in integer numbers. To do that I use vectors that store each digit individually. I want to write the whole thing as a function that prints out the repeating patterns of the number. The numbers are mostly 12 digits long.

An example:
The number is 057 987 051 2057
I want the function to print out:
057
05
It should also only print out the longest recurrent pattern. I'm currently stuck on how to implement the whole thing in C++. I would also like to know if there are any libraries that support the feature I'm looking for.

Thanks in advance!

EDIT:

for (vector<int>::iterator it = m_number.begin(); it != m_number.end(); ++it) {
    int follower = *(it + 1);
    for (vector<int>::iterator jt = it + 1; jt != m_number.end(); ++jt) {
        if (*jt == *it) {
            if (*(jt + 1) == follower)
                cout << *jt;
            }
        }
    cout << endl;
    }

This is what I've tried so far. This here obviously doesn't work yet but I hope it gives you an idea about what I want the function to do. I try to use two for-loops that iterate over the m_number vector (that contains the integer number I'm trying to check btw.).

Answer 1

You could use an unordered_map to start with.

#include <iostream>
#include <iomanip>
#include <unordered_map>

int main() {
    std::string str = "0579870512057";
    // a map of substrings and the number of times they appear
    std::unordered_map<std::string, size_t> pm;

    for(auto a=str.begin(); a!=str.end()-1; ++a) {
        for(auto b=a+1; b!=str.end(); ++b) {
            // std::string(a, b+1) creates the substring from your iterators
            // the unordered_map::operator[] creates a key, value pair
            // if the key doesn't exist (value is default constructed)
            // ++ increases the value by 1
            ++pm[ std::string(a, b+1) ];
        }
    }
    // display the number of times each substring appears (if it appeared more than once)
    // and display the length (size) of each
    for(auto& p : pm) {
        if(p.second>1)
            std::cout << std::setw(3) << p.second << " "
                      << std::setw(12) << p.first.size() << " " << p.first << "\n";
    }
}

---

A slightly more complicated way is to create a custom set that keeps the recurring patterns sorted from longest to shortest but it has the advantage that you'll know that the first pattern in the result will be the longest. It also does not make any copies of the original input except for the patterns found.

#include <iostream>
#include <set>

struct comp { // a custom comparison class to sort the result
    bool operator()(const std::string& a, const std::string& b) const {
        if(b.size()==a.size()) return a < b; // lowest "value" when length is equal
        else return b.size() < a.size();     // but longest pattern goes first
    }      // note  b  before  a  when comparing sizes
};

using string_pattern_set = std::set<std::string, comp>; // custom set type using "comp"

string_pattern_set get_recurring_patterns(const std::string& str) {
    string_pattern_set sorted_result;

    for(size_t len=str.size()-1; len>0; --len) {
        auto end = str.end()-len;
        for(auto pos=str.begin(); pos<end; ++pos) {
            for(auto check=pos+1; check<=end; ++check) {
                if(std::equal(pos, pos+len, check)) {
                    sorted_result.emplace(pos, pos+len);
                    break;
                }
            }
        }
    }
    return sorted_result;
}

int main() {
    string_pattern_set res = get_recurring_patterns("0579870512057");
    if(res.size())
        std::cout << "the longest recurring pattern is "
                  << res.begin()->size() << " char(s)\n";
    // display all patterns from longest to shortest
    for(auto& str : res) std::cout << str << "\n";
}

---

A third option, if you are really worried about memory consumption, would be to not store the recurring strings at all but to store the begin and end iterators for the matching substrings. This approach works well when the recurring patterns are expected to be long and plentiful.

#include <iostream>
#include <set>
#include <algorithm>
#include <iterator>

// type to store begin and end iterators for matching patterns
using strits = std::pair<std::string::const_iterator, std::string::const_iterator>;

struct comp { // a custom comparison class to sort the result
    bool operator()(const strits& a, const strits& b) const {
        if((b.second-b.first)==(a.second-a.first)) // lowest "value" when length is equal
            return std::lexicographical_compare(a.first, a.second, b.first, b.second);
        else // but longest pattern goes first
            return (b.second-b.first) < (a.second-a.first);
    }      // note  b  before            a  when comparing sizes
};

using string_pattern_set = std::set<strits, comp>; // custom set type using "comp"

template<bool LONGEST_ONLY = false, bool BIG_STRING = false>
string_pattern_set get_recurring_patterns(const std::string& str) {
    string_pattern_set sorted_result;

    for(size_t len=str.size()-1; len>0; --len) {
        auto end = str.end()-len;
        for(auto begin=str.begin(); begin<end; ++begin) {
            if constexpr (BIG_STRING) {
                // skip patterns already found to be recurring.
                // in C++20, use set::contains instead
                if(sorted_result.find(strits(begin, begin+len))!=sorted_result.end())
                    continue;
            }
            for(auto check=begin+1; check<=end; ++check) {
                if(std::equal(begin, begin+len, check)) {
                    sorted_result.emplace(begin, begin+len);
                    break;
                }
            }
        }
        if constexpr (LONGEST_ONLY)
            if(!sorted_result.empty()) break;
    }
    return sorted_result;
}

int main() {
    string_pattern_set res = get_recurring_patterns("0579870512057");

    if(res.size()) {
        const auto& [begin, end] = *res.begin();
        std::cout << "the longest recurring pattern is "
                  << (end - begin)<< " char(s)\n";
    }

    // display all patterns from longest to shortest
    for(const auto& [begin, end] : res) {
        std::copy(begin, end, std::ostream_iterator<char>(std::cout));
        std::cout << "\n";
    }
}

Answer 2

You might use something like:

std::set<std::vector<int>> GetRepetitingPatterns(const std::vector<int>& v)
{
    std::set<std::vector<int>> res;
    for (std::size_t size = v.size() - 1; size != 0; --size) {
        std::set<std::vector<int>> s;

        for (std::size_t i = 0; i + size != v.size() + 1; ++i) {
            auto [it, inserted] = s.emplace(v.begin() + i, v.begin() + i + size);
            if (!inserted) {
                res.insert(*it);
            }
        }
#if 1 // Longest only
        if (!res.empty()) {
            return res;   
        }
#endif
    }
    return {};
}

Demo

and for variation (all/longest and min size): Demo

Answer 3

Here is a first way of doing it :

for (size_t i = 0; i < m_numbers.size(); i++) {
    // Look for patterns starting everywhere in the following numbers
    for (size_t j = i+1; j < m_numbers.size(); j++) {
      // Pattern storing
      std::vector<int> pattern;

      // Condition to stop the search
      bool valid_pattern = true;

      // Variable for the while loop
      int offset = 0;
      while (valid_pattern && j+offset < m_numbers.size()) {
        // If the numbers are equal, continue the pattern, else, stop the search
        if(m_numbers[i+offset] == m_numbers[j+offset]){
          pattern.push_back(m_numbers[i+offset]);
        } else {
          valid_pattern = false;
        }
        offset++;
      }

      // If the pattern has at least two numbers, output it to the console
      if(pattern.size() > 1){
        for (size_t idx = 0; idx < pattern.size(); idx++) {
          std::cout << pattern[idx];
        }
        std::cout << std::endl;
      }
    }
  }