字符串处理/有限状态机

发表于 更新于 分类于 Valine： 本文字数： 2.9k 阅读时长 ≈ 3 分钟

切片

和python中的定义一致，习惯了，比按长度取字串方便，而且负下标也很方便

1
2
3
4
5
string slice(const string& s, int b, int e) {
    if(b<0) b += s.size();
    if(e<0) e += s.size();
    return s.substr(b, e-b);
}

去掉字符串前后的空白

python里叫strip，其他语言多叫trim

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
string strip(const string& s, const string& space=" ") {
    const char* p = &s[0];
    const char* q = &s[0]+s.size();
    for(; p<q; p++) {
        if(space.find(*p) == -1) break;
    }
    if(p<q) q--;
    for(; p<q; q--) {
        if(space.find(*q) == -1) {
            q++;
            break;
        }
    }
    return string(p, q);
}

切开(split)和拼接(join)

支持切开同时strip掉空白字符，比先切开再strip要快，还可以选择是否丢弃切开后空的元素。

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
vector<string> split(const string& s, const string& delim, const string& stripchars="", bool drop_empty=false) {
    vector<string> result;
    int b = 0;
    int e = 0;
    int i = b;
    int state = 0;
    do {
        bool isspace = (stripchars.find(s[i]) != -1);
        bool isdelim = (s[i]=='\0' || delim.find(s[i]) != -1);
        if(isdelim) {
            if(e != b || !drop_empty) {
                result.emplace_back(string(&s[b], &s[e]));
            }
            state = 0;
            e = b = i + 1;
        } else if(isspace) {
            if(state == 0) {
                e = b = i + 1;
            }
        } else {
            state = 1;
            e = i + 1;
        }
        if(s[i]=='\0') break;
        i++;
    } while(true);
    return result;
}

string join(vector<string> arr, const string& delim) {
    if(arr.empty()) return "";
    stringstream ss;
    ss << arr[0];
    for(int i=1;i<arr.size();i++) {
        ss << delim << arr[i];
    }
    return ss.str();
}

有限状态机

竞赛中字符串的题目可以考虑先画出状态转换图，然后基于有限状态自动机求解，包括上面的split函数，找不到之前的模板了，我重写的时候就是基于有限状态自动机

刚写出来是下面这样，很多重复代码，一共四个状态，完全就是按状态转移写的，非常清晰。

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
vector<string> split(const string& s, const string& delim, const string& stripchars="", bool drop_empty=false) {
    vector<string> result;
    int b = 0;
    int e = 0;
    int i = b;
    int state = 0;
    do {
        bool isspace = (stripchars.find(s[i]) != -1);
        bool isdelim = (s[i]=='\0' || delim.find(s[i]) != -1);
        switch(state) {
        case 0:
            if(isdelim) {
                if(e != b || !drop_empty) {
                    result.emplace_back(string(&s[b], &s[e]));
                }
                state = 0;
                e = b = i + 1;
            } else if(isspace) {
                state = 1;
                e = b = i + 1;
            } else {
                state = 2;
                e = i + 1;
            }
            break;
        case 1:
            if(isdelim) {
                if(e != b || !drop_empty) {
                    result.emplace_back(string(&s[b], &s[e]));
                }
                state = 0;
                e = b = i + 1;
            } else if(isspace) {
                state = 1;
                e = b = i + 1;
            } else {
                state = 2;
                e = i + 1;
            }
            break;
        case 2:
            if(isdelim) {
                if(e != b || !drop_empty) {
                    result.emplace_back(string(&s[b], &s[e]));
                }
                state = 0;
                e = b = i + 1;
            } else if(isspace) {
                state = 3;
            } else {
                state = 2;
                e = i + 1;
            }
            break;
        default:
            if(isdelim) {
                if(e != b || !drop_empty) {
                    result.emplace_back(string(&s[b], &s[e]));
                }
                state = 0;
                e = b = i + 1;
            } else if(isspace) {
                state = 3;
            } else {
                state = 2;
                e = i + 1;
            }
            break;
        }
        if(s[i]=='\0') break;
        i++;
    } while(true);
    return result;
}

当然还有可能表面是个字符串的问题，实际上是个动态规划问题或者搜索问题。