USACO-T043: Contact

/*
ID: mickyta1
TASK: contact
LANG: C++
*/

#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
typedef pair<int, int> pii;

const int L = 2e5 + 5;

map<int, int> mp;
vector<pii> fq;
vector<int> ans;
int len;
char str[L];

bool comp(const pii &lhs, const pii &rhs){
    if(lhs.s != rhs.s){
        return lhs.s > rhs.s;
    }
    return lhs.f < rhs.f;
}

int charToInt(char c){
    return c - '0' + 1;
}

void base3ToBit(int x){
    if(x == 0){
        return;
    }
    base3ToBit(x / 3);
    cout << x % 3 - 1;
}

void addWordLength(int l){
    int hsh = 0;
    int base = 1;
    for(int i = 1; i <= l; ++i){
        hsh *= 3;
        hsh += charToInt(str[i]);
        if(i != 1){
            base *= 3;
        }
    }
    ++mp[hsh];
    for(int i = l + 1; i <= len; ++i){
        hsh -= base * charToInt(str[i - l]);
        hsh *= 3;
        hsh += charToInt(str[i]);
        ++mp[hsh];
    }
}

void printAns(){
    int upb = ((int)ans.size() + 5) / 6;
    for(int i = 0; i < upb; ++i){
        int j;
        for(j = 0; j < 5 && 6 * i + j < (int)ans.size() - 1; ++j){
            base3ToBit(ans[6 * i + j]);
            cout << ' ';
        }
        base3ToBit(ans[6 * i + j]);
        cout << '\n';
    }
}

int main(){
    freopen("contact.in", "r", stdin);
    freopen("contact.out", "w", stdout);

    int lwb, upb, limRnk;
    scanf("%d%d%d", &lwb, &upb, &limRnk);
    len = 1;
    while(scanf(" %s", str + len) != EOF){
        len += strlen(str + len);
    }
    --len;
    upb = min(upb, len);
    for(int i = lwb; i <= upb; ++i){
        addWordLength(i);
    }
    for(pii p : mp){
        fq.push_back(p);
    }
    sort(fq.begin(), fq.end(), comp);
    int rnk = 0;
    int lst = 0;
    for(pii &p : fq){
        if(rnk > limRnk){
            break;
        }
        int x = p.f;
        int f = p.s;
        if(f != lst){
            if(lst != 0){
                cout << lst << '\n';
                printAns();
            }
            lst = f;
            ++rnk;
            ans.clear();
        }
        ans.push_back(x);
    }
    if(rnk <= limRnk){
        cout << lst << '\n';
        printAns();
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}