Minimum length of specific substrings

Question

Given the string \$s\$. It is required to answer n queries. The \$i\$th query consists of an integer \$k_i\$ and a string \$m_i\$, the answer is the minimum length of the string \$t\$ such that \$t\$ is a substring of \$s\$ and the string \$m_i\$ appears in \$t\$ as a substring at least \$k_i\$ times. A substring of a string is any sequence of consecutive characters in this string. It is guaranteed that for any two queries the strings mi from these queries are different.

Input format: The first line contains the string s \$\left ( 1\leq |s|\leq 10^5 \right )\$. The second line contains the integer n (\$1 n \leq 10^5\$). Each of the next \$n\$ lines contains an integer \$k_i\$ (\$1 \leq k_i \leq |s|\$) and a non-empty string \$m_i\$ - parameters of the request with number \$i\$ . All lines in the input consist only of lowercase letters of the Latin alphabet. The total length of all lines in the input does not exceed \$10^5\$. All \$m_i\$ are different.

Output format: For each request, print the response to it on a separate line. If the string \$m_i\$ occurs s less than \$k_i\$ times, print \$-1\$.

Example:

aaaaa
5
3a
3 aa
2 aaa
3 aaaa
1 aaaaa

Answer:

3
4
4
-1
5

My code:

#include <iostream>
#include <string>
#include <vector>
#include <climits>

using namespace std;

int cntOcc(const string& s, const string& t) {
    int cnt = 0;
    size_t pos = s.find(t);
    while (pos != string::npos) {
        cnt++;
        pos = s.find(t, pos + 1);
    }
    return cnt;
}

int minLen(const string& s, const string& t, int k) {
    int n = s.size();
    int t_len = t.size();
    if (cntOcc(s, t) < k) return -1;

    int min_len = INT_MAX;
    for (int i = 0; i <= n - t_len; ++i) {
        int occ = 0;
        for (int j = i; j < n; ++j) {
            if (s.substr(j, t_len) == t) occ++;
            if (occ == k) {
                min_len = min(min_len, j - i + t_len);
                break;
            }
        }
    }
    return min_len == INT_MAX ? -1 : min_len;
}

int main() {
    string s;
    int n;
    cin >> s >> n;

    vector<int> k(n);
    vector<string> m(n);

    for (int i = 0; i < n; ++i) {
        cin >> k[i] >> m[i];
    }

    for (int i = 0; i < n; ++i) {
        int res = minLen(s, m[i], k[i]);
        cout << res << endl;
    }

    return 0;
}

The code was quite slow, and I tried to speed it up by using two pointers (two windows) and hashing to count occurrences of the substring

#include <iostream>
#include <string>
#include <vector>
#include <climits>

using namespace std;

int cntOcc(const string& s, const string& t) {
    int cnt = 0;
    size_t pos = s.find(t);
    while (pos != string::npos) {
        cnt++;
        pos = s.find(t, pos + 1);
    }
    return cnt;
}

int minLen(const string& s, const string& t, int k) {
    int n = s.size();
    int t_len = t.size();
    if (cntOcc(s, t) < k) return -1;

    int l = 0, r = 0;
    int occ = 0;
    int min_len = INT_MAX;

    while (r < n) {
        if (s.substr(r, t_len) == t) occ++;
        while (occ >= k) {
            min_len = min(min_len, r - l + t_len);
            if (s.substr(l, t_len) == t) occ--;
            l++;
        }
        r++;
    }
    return min_len == INT_MAX ? -1 : min_len;
}

int main() {
    string s;
    int n;
    cin >> s >> n;

    vector<int> k(n);
    vector<string> m(n);

    for (int i = 0; i < n; ++i) {
        cin >> k[i] >> m[i];
    }

    for (int i = 0; i < n; ++i) {
        int res = minLen(s, m[i], k[i]);
        cout << res << endl;
    }

    return 0;
}

But, the code did not run much faster. It helped, but not significantly. Is there a good code optimization or algorithm for the task?

Answer 1

It's strange that no one paid attention to this problem, since it is quite interesting

The code itself is quite optimal and I don’t see what can be improved here. No matter what functions we use here, this algorithm will not work faster. I had to do a little digging on the internet to find a new algorithm (new to me)

This algorithm is called "Suffix Array" - it is an array of all suffixes of a string, sorted in lexicographical order. It allows you to quickly find all occurrences of a substring in a string. The suffix array can be built in \$O\left ( n\log n \right )\$ time and then searching for any substring can be done in \$O\left ( m\log n \right )\$, where \$n\$ is the length of the string and \$m\$ is the length of the substring

The purpose of the code is to find the minimum length of a substring in the string \$s\$ that contains at least \$k\$ occurrences of a given substring \$t\$. This is useful in tasks related to text analysis, pattern recognition and bioinformatics.

1. findAllOccurrences

   • Finds all occurrences of the substring t in the string s and returns their positions.
   • The function uses the find method to find the position of the first occurrence of the substring t in the string s. It then continues to search for the next occurrences in a loop, starting from the position after the found occurrence, and adds all positions to the vector.

2. findMinLength

   • Finds the minimum length of a substring in a string s that contains at least k occurrences of the substring t.
   • The function first uses findAllOccurrences to get all the positions of occurrences of the substring t in the string s. It then checks whether there are enough occurrences found to satisfy condition k. If so, the function uses the sliding window method to find the minimum length of a substring including k occurrences of t.

3. main

   • The main function, which reads the input data, calls the necessary functions and outputs the results.
   • The function reads the string s and the number of requests n. It then reads each value of k and the corresponding substring m[i]. For each request, the findMinLength function is called, the result of which is displayed on the screen.

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <climits>

using namespace std;

vector<int> findAllOccurrences(const string &s, const string &t) {
    vector<int> positions;
    size_t pos = s.find(t);
    while (pos != string::npos) {
        positions.push_back(pos);
        pos = s.find(t, pos + 1);
    }
    return positions;
}

int findMinLength(const string &s, const string &t, int k) {
    vector<int> positions = findAllOccurrences(s, t);

    if (positions.size() < k) return -1;

    int min_len = INT_MAX;
    for (int i = 0; i + k - 1 < positions.size(); ++i) {
        int current_len = positions[i + k - 1] - positions[i] + t.size();
        min_len = min(min_len, current_len);
    }

    return min_len;
}

int main() {
    string s;
    int n;
    cin >> s >> n;

    vector<int> k(n);
    vector<string> m(n);

    for (int i = 0; i < n; ++i) {
        cin >> k[i] >> m[i];
    }

    for (int i = 0; i < n; ++i) {
        int result = findMinLength(s, m[i], k[i]);
        cout << result << endl;
    }

    return 0;
}

Links to resources I used and short explanations from me

1. Substring_Search_Algorithms

   • The repository contains implementations of various substring search algorithms, such as the Boyer-Moore algorithm and the naive method.
   • Algorithms from this repository can be used for comparison with the current implementation and possibly for further optimization of the code.

2. PySubstringSearch

   • A Python library for fast substring searching, written in C++ using a suffix array.
   • This library demonstrates the use of a suffix array to efficiently search for substrings, which can be useful for further study and improving the performance of the code.

3. String-algorithms

   • A collection of linear algorithms for searching and comparing strings, including algorithms for constructing suffix arrays and searching for the largest common prefix.
   • The algorithms in this repository provide additional methods for efficiently searching substrings and manipulating strings, which may be useful for improving the current implementation.

Perhaps there are other algorithms that I have not heard of that can produce results faster. I would be interested to read about them

Answer 2

Please don't drag the whole of std into the global namespace with using namespace std; - that completely eliminates all the benefits of namespacing and makes your code less predictable.

Functions that require std::string as input are inflexible. If we were to accept std::basic_string_view<> we'd support all character types and avoid having to construct string objects in many cases.

The function name cnt0cc is completely uninformative. Is it even supposed to be part of the public interface, or would it be better hidden away in anonymous namespace, or perhaps as a lambda within the one function that calls it?

int cnt is a poor choice for a count, even if we're told it won't exceed 32767 - std::size_t is a more natural fit, and avoids one of the compiler warnings this code provokes. And please pick a less offensive name for it.

It's strange that we do a separate counting pass (especially when we just compare against k, missing an opportunity to finish early). As we're performing this pass, why not record the start positions in a std::queue of length k, giving us the length of each candidate substring as we go? That would look like this (with the other improvements mentioned above):

#include <queue>
#include <string_view>

template<typename S1, typename S2>
requires requires(S1 a, S2 b) { std::basic_string_view(a).find(std::basic_string_view(b)); }
std::size_t min_length(const S1& s, const S2& t, std::size_t match_count)
{
    std::basic_string_view haystack(s);
    std::basic_string_view needle(t);

    if (needle.empty()) {
        // occurs infinitely many times between chars
        return 0;
    }

    // record most recent match_count start positions
    std::queue<std::size_t> starts;

    auto minimum = haystack.npos;
    auto pos = haystack.find(needle);
    while (pos != haystack.npos) {
        starts.push(pos);
        if (starts.size() == match_count) {
            auto start = starts.front();
            auto end = pos + needle.length();
            if (auto length = end - start;  length < minimum) {
                minimum = length;
            }
            starts.pop();
        }
        pos = haystack.find(needle, pos + 1);
    }
    return minimum;
}

---

Always check for success of streaming input before using the streamed-to values:

    std::string s;
    std::size_t n;
    cin >> s >> n;
    if (!std::cin) {
        std::cerr << "Invalid input\n";  // TODO: friendly re-read
        return EXIT_FAILURE;
    }

There's no need to flush output using std::endl immediately before program exit - std::cout's destructor will flush anyway.

We don't need return 0; at the end of main() - just running off the end of the function has the same effect (for main() only, not for other functions!).

---

It would have been easier to review the code if the unit tests had been provided as part of the review. Even some basic tests such as these help show what's expected of the code:

#include <gtest/gtest.h>

TEST(min_length, empty)
{
    EXPECT_EQ(0, min_length("", "", 3));
    EXPECT_EQ(-1, min_length("", "a", 3));
}

TEST(min_length, aaaaa)
{
    EXPECT_EQ(0, min_length("aaaaa", "", 3));
    EXPECT_EQ(3, min_length("aaaaa", "a", 3));
    EXPECT_EQ(4, min_length(L"aaaaa", L"aa", 3));
    EXPECT_EQ(-1, min_length("aaaaa", "ba", 3));
}

TEST(min_length, ababa)
{
    EXPECT_EQ(0, min_length("ababa", "", 3));
    EXPECT_EQ(5, min_length("ababa", "a", 3));
    EXPECT_EQ(4, min_length(u8"ababa", u8"ab", 2));
    EXPECT_EQ(5, min_length("ababa", "aba", 2));
}

TEST(min_length, aabbabaa)
{
    EXPECT_EQ(4, min_length("aabbabaa", "b", 3));
    EXPECT_EQ(4, min_length("aabbabaa", "a", 3));
    EXPECT_EQ(8, min_length("aabbabaa", "aa", 2));
    EXPECT_EQ(2, min_length("aabbabaa", "b", 2));
    EXPECT_EQ(4, min_length("aabbabaa", "b", 3));
    EXPECT_EQ(5, min_length("aabbabaa", "ab", 2));
}