Contact

Solution Approach

Counting All Substrings

Since pattern lengths are at most 12, each pattern fits in a 12-bit integer (values 0 to $2^{12} - 1 = 4095$). We maintain a 2D frequency table $\mathtt{cnt}[\ell][v]$ for length $\ell$ and value $v$.

For each starting position $i$, build the pattern incrementally:

val = 0
  for len = 1 to min(b, n - i):
      val = val * 2 + S[i + len - 1]
      if len >= a:
          cnt[len][val]++

Sorting and Output

Collect all (frequency, length, value) triples with positive frequency. Sort by frequency descending, then length ascending, then value ascending. Output the top $k$ frequency groups.

C++ Solution

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

char buf[200005];
int cnt[13][4096]; // cnt[len][val]

int main() {
    int a, b, k;
    scanf("%d %d %d", &a, &b, &k);

    // Read binary string (may span multiple lines)
    int n = 0;
    char line[100];
    while (scanf("%s", line) == 1) {
        for (int i = 0; line[i]; i++)
            buf[n++] = line[i] - '0';
    }

    memset(cnt, 0, sizeof(cnt));

    // Count all patterns of length a..b
    for (int i = 0; i < n; i++) {
        int val = 0;
        for (int len = 1; len <= b && i + len <= n; len++) {
            val = val * 2 + buf[i + len - 1];
            if (len >= a)
                cnt[len][val]++;
        }
    }

    // Collect patterns with positive frequency
    struct Pattern {
        int freq, len, val;
    };
    vector<Pattern> patterns;
    for (int len = a; len <= b; len++)
        for (int v = 0; v < (1 << len); v++)
            if (cnt[len][v] > 0)
                patterns.push_back({cnt[len][v], len, v});

    // Sort: frequency descending, then length ascending, then value ascending
    sort(patterns.begin(), patterns.end(), [](const Pattern& x, const Pattern& y) {
        if (x.freq != y.freq) return x.freq > y.freq;
        if (x.len != y.len) return x.len < y.len;
        return x.val < y.val;
    });

    // Output top k frequency groups
    int groups = 0, i = 0;
    while (i < (int)patterns.size() && groups < k) {
        int curFreq = patterns[i].freq;
        printf("%d\n", curFreq);

        int lineCount = 0;
        while (i < (int)patterns.size() && patterns[i].freq == curFreq) {
            if (lineCount > 0) printf(" ");
            // Print binary representation with correct number of digits
            int len = patterns[i].len;
            int val = patterns[i].val;
            char bits[13];
            for (int j = len - 1; j >= 0; j--) {
                bits[j] = '0' + (val & 1);
                val >>= 1;
            }
            bits[len] = '\0';
            printf("%s", bits);
            lineCount++;
            i++;
        }
        printf("\n");
        groups++;
    }

    return 0;
}

Complexity Analysis

• Time complexity: $O(n \cdot b)$ for counting, where $b \le 12$. Effectively $O(n)$. Sorting the patterns takes $O(P \log P)$ where $P \le (b - a + 1) \cdot 2^b \le 12 \cdot 4096 = 49{,}152$, which is negligible.

• Space complexity: $O(b \cdot 2^b + n)$: the frequency table plus the input string.