题解 | 子串计算

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <set>
using namespace std;
int count_subsequence(string& orig_seq, string& sub_seq) {
    if (orig_seq.length() < sub_seq.length())
        return 0;
    int start = 0, index1 = 0, index2 = 0, count = 0;
    while (start <= (orig_seq.length() - sub_seq.length())) {
        if (index2 == sub_seq.length())
            count++, start++, index1 = start, index2 = 0;
        if (orig_seq[index1] == sub_seq[index2])
            index1++, index2++;
        else
            start++, index1 = start, index2 = 0;
    }
    return count;
}
string int_to_binary_str(int num, int digits) {
    string result(digits, '0');
    for (int i = digits - 1; i >= 0; i--) {
        result[i] += (num & 1);
        num >>= 1;
    }
    return result;
}
vector<string> zero_one_strs(int num) {
    if (num <= 0)
        return vector<string>();
    vector<string> result(int(pow(2, num)));
    for (int i = 0; i < result.size(); i++) {
        result[i] = int_to_binary_str(i, num);
    }
    return result;
}
class SubSeq {
  public:
    string str;
    int count;
    SubSeq(string& str, int count) {
        this->str = str;
        this->count = count;
    }
    bool operator<(const SubSeq& subseq) const {
        return str < subseq.str;
    }
};
set<SubSeq> count_subsequence(string& str, int greater_times) {
    set<SubSeq> result;
    for (int i = 1; i < str.length(); i++) {
        vector<string> strs = zero_one_strs(i);
        for (int j = 0; j < strs.size(); j++) {
            int count = count_subsequence(str, strs[j]);
            if (count > greater_times)
                result.insert(SubSeq(strs[j], count));
        }
    }
    return result;
}
void print_set(set<SubSeq>& subset) {
    for (set<SubSeq>::iterator it = subset.begin(); it != subset.end(); ++it) {
        cout << it->str << " " << it->count << endl;
    }
}
int main() {
    string str;
    while (cin >> str) {
        set<SubSeq> subset = count_subsequence(str, 1);
        print_set(subset);
    }
}