题解 P1321 【单词覆盖还原】

· · 题解

争做最简洁最易懂的题解！全部代码23行。不一定最短，但一定最好懂。

boy和girl的计数，分别是以下几种情况： boy：boy -oy bo- b-- -o- --y

girl：girl gir- -irl gi-- -ir- --rl g--- -i-- --r- ---l

因此，只要找到符合这几种情况的的就行了。如果能将这几种情形列举或统计出来，就是比较直接的办法。

但是，如果用s[i-1]和s[i]来判断有b无o、有o无y……，列举的情形非常多，容易漏。如果按以上几种情形统计，虽然列举情形少，但容易互相干扰。比如，这次找到了boy，下次找oy，两者结果没法区分。

怎样既统计次数，又防止干扰呢？可使用边找子串、边计数、边更新原字符串的办法。找到目标子串后，计数，再把目标子串整段替换。

注意，要先查找长的子串、再找短些的子串，最后找单个字符的子串，因为短的子串包含在长的子串中。比如先找oy再找boy，那么boy这个子串会被多次计算，而反过来先找boy，boy整个被替换后，再也不会有干扰了。

要用到字符串操作的几个函数。

s.replace(fi, len, "#")，表示把fi这个位置开始、长度为len的子替换为#。这里不要用erase操作，因为会引发下标变化。

s.find(t,k)，表示在k位置后查找子串t，能找到返回下标，找不到返回-1。如果需要连续查找，就使用循环操作，从k+1处再找。

#include <bits/stdc++.h>
using namespace std;
string s;
int kb, kg;
int cs(string t)//在字串s中找子串t
{
    int k = 0, len = t.size(), fi = s.find(t);
    while (fi != -1)//只要有这个子串
    {
        k++;//计数
        s.replace(fi, len, "*"); //等长替换，不要用erase
        fi = s.find(t, fi + 1);//下个位置开始找
    }
    return k;
}
int main()
{
    cin >> s;
    kb = cs("boy") + cs("bo") + cs("oy") + cs("b") + cs("o") + cs("y");
    kg = cs("girl") + cs("gir") + cs("irl") + cs("gi") + cs("ir") + cs("rl") + cs("g") + cs("i") + cs("r") + cs("l");
    cout << kb <<endl << kg << endl;
    return 0;
}