Alg/test.cpp at main · zongfeijing/Alg · GitHub

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
#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_set>

using namespace std;

int bp(string &s, unordered_set<string> &flag, int start)
{
    if (start == s.size())
        return 0;

    int res = 0;
    string cur;

    for (int end = start; end < s.size(); ++end)
    {
        cur.push_back(s[end]);

        if (flag.count(cur))
            continue;

        flag.insert(cur);

        res = max(res, 1 + bp(s, flag, end + 1));

        flag.erase(cur);
    }

    return res;
}

int get_nums(string s)
{
    unordered_set<string> flag;

    return bp(s, flag, 0);
}

int main()
{
    string s = "abacaba";

    int res = get_nums(s);

    cout << "Res is " << res << endl;
}