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

struct PointS {
    int index;
    int count;
};
class Solution {
public:
    int ans;
    vector<PointS> seq;
    int numDistinct(string S, string T) {
        ans = 0;
        if(T.length() <= 0)return ans;
        seq.clear();
        for(int i = 0;i < S.length();i++) {
            if(S[i] == T[T.length()-1]) {
                PointS item;
                item.index = i;
                item.count = 1;
                seq.push_back(item);
            }
        }
        matchStep(T.length() - 2,S,T,seq);
        return ans;
    }
private:
    void matchStep (int now,string S,string T,vector<PointS>& seq) {
        if(now == -1) {
            for(int i = 0;i < seq.size();i++) {
                PointS item = seq[i];
                ans += item.count;
            }
            return ;
        }
        vector<PointS> seq_c;
        seq_c.clear();
        int i = 0;
        int bottom = 0;
        int sum = 0;
        for(int i = 0;i < seq.size();i++)
            sum += seq[i].count;
        while(i < seq.size()) {
            for(int j = bottom;j < seq[i].index;j++) {
                if(S[j] == T[now]) {
                    PointS item;
                    item.index = j;
                    item.count = sum;
                    seq_c.push_back(item);
                }
            }
            bottom = seq[i].index;
            sum -= seq[i].count;
            i++;
        }
        seq.clear();
        matchStep (now - 1,S,T,seq_c);
    }
};