1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

class Solution {
public:
    bool *flag;
    int len;
    vector<int> result;
    vector<int> copy;
    int sum;
    vector<int> findSubstring(string S, vector<string> &L) {
        result.clear();
        if(L.size() <= 0) return result;
        map<string,int> mapr;
        mapr.clear();
        vector<vector<int>> rtable;
        rtable.clear();
        len = L[0].size();
        map<string,int>::iterator it;
        for(int i = 0; i < L.size(); i++) {
            it = mapr.find(L[i]);
            if(it != mapr.end()) {
                it->second += 1;
            }
            else
                mapr.insert(map<string,bool>::value_type(L[i],1));
        }
        copy.clear();
        sum = 0;
        for(it = mapr.begin(); it != mapr.end(); it++) {
            copy.push_back(it->second);
            sum += it->second;
        }
        bfs(mapr, S, 0);
        return result;
    }
private:
    void bfs(map<string,int> &mapr, string &S, int start) {
        if(S.length() - start < sum * len) return;
        int position;
        map<string,int>::iterator it;
        int min = S.length();
        for(it = mapr.begin(); it != mapr.end(); it++) {
            string item = it->first;
            if((position = S.find(item,start)) == string::npos) return;
            if(position < min)
                min = position;
        }
        int i = 0;
        int end;
        if(bfsStep(mapr,min,S,end)) {
            end = min + 1;
            result.push_back(min);
        }
        end = min + 1;
        if(end >= S.length()) return;
        return bfs(mapr, S, end);
    }
    void resetMapr(map<string,int> &mapr) {
        int i = 0;
        map<string,int>::iterator it;
        for(it = mapr.begin(); it != mapr.end(); it++) {
            it->second = copy[i++];
        }
    }
    bool bfsStep(map<string,int> &mapr, int pos, string &S, int &end) {
        int count = 0;
        map<string,int>::iterator it;
        int i;
        for(i = pos; i < S.length(); i+=len) {
            it = mapr.find(string(S, i, len));
            if(it == mapr.end() || it->second <= 0) {
                end = i+len;
                resetMapr(mapr);
                return false;
            }
            it->second--;
            count++;
            if(count == sum) {
                resetMapr(mapr);
                return true;
            }
        }
        resetMapr(mapr);
        if(count == sum) return true;
        end = i;
        return false;
    }
};