AtCoder题解 —— AtCoder Regular Contest 108 —— B - Abbreviate Fox

给一个长度 N 和对应长度的字符串 S，snuke 可以执行以下操作任意次：删除子字符串 fox。问最后字符串 s 的长度是多少。

题目分析

看完题目，我觉得可以直接使用 STL 的 string 类中的 find() 和 erase() 函数对字符串直接操作。极限情况下字符串长度就是 2e5，理论上应该可以在 1 秒内完成。

使用 STL 的 string

//https://atcoder.jp/contests/arc108/tasks/arc108_b
//B - Abbreviate Fox
#include <bits/stdc++.h>using namespace std;int main() {
#if 1//这些代码需要提交到OJ，本地调试不使用ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#endifint n;string s;cin>>n>>s;size_t pos;while (string::npos != (pos=s.find("fox"))) {s.erase(pos, 3);}cout<<s.length()<<"\n";#if 0//这些代码不需要提交到OJ，本地调试使用system("pause");
#endifreturn 0;
}

结果 AtCoder 测试后的结果如下。

其中，hand_03.txt 使用了 2205ms 超时；random_04.txt 使用了 1218ms；random_06.txt 使用了 1008ms；random_10.txt 使用了 1454ms。看来 erase() 函数的效率一般。

我们必须优化代码，不能使用 string 类了。我们需要一个 O(N) 时间复杂度的算法，也就是自己来遍历字符串，同时对数据进行操作。

算法分析

我们来分类讨论以下每个字符可能性，假设当前字符为 s[i]。

• s[i] 不是 f、o、x 中的其他小写字符。
• s[i] 是字符 f。
• s[i] 是字符 o。
• s[i] 是字符 x。

为了处理字符方便，我们可以使用浪费空间的方式，也就是多一个 N 长度的空白字符串，用来表示最后生成的字符串，我们记为字符串 t，这样我们可以得出如下结论。

• s[i] 不是 f、o、x 中的其他小写字符。将字符拷贝到 t 中。即 t[idx++]=s[i]。
• s[i] 是字符 f。将字符拷贝到 t 中。即 t[idx++]=s[i]。
• s[i] 是字符 o。将字符拷贝到 t 中。即 t[idx++]=s[i]。
• s[i] 是字符 x。说明有可能前面的字符构成 fox 字符串，可以删除，因此需要和前面的两个字符进行合并比较。如果是构成 fox 则删除 t 中的数据。如果不构成，拷贝字符到 t 中即可。

这样，我们就将算法的复杂度变成了 O(N)。

其实不删除字符串 t 中的数据也是可以的，只需要控制 idx 指针即可。另外我们发现，对所有的字符都需要将 s[i] 拷贝到 t[idx] 这个位置中，我们可以将情况进一步简化，也就是所有的字符都拷贝到 t[idx] 中，如果碰到字符 x 才向前回溯处理指针。

数据范围估计

N 的最大值为 2e5，因此用 int 可以表达。

AC 参考代码

//https://atcoder.jp/contests/arc108/tasks/arc108_b
//B - Abbreviate Fox
#include <bits/stdc++.h>using namespace std;//如果提交到OJ，不要定义 __LOCAL
//#define __LOCALint main() {
#ifndef __LOCAL//快读代码ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#endifint n;string s;cin>>n>>s;string t(n, ' ');int idx=0;int cnt=0;//统计删除几个for (int i=0; i<n; i++) {t[idx++]=s[i];if ('x'==s[i]) {//字符 xif (idx>=3 && 'o'==t[idx-2] && 'f'==t[idx-3]) {idx -= 3;cnt += 3;//删除了 3 个字符}}}cout<<n-cnt<<"\n";#ifdef __LOCAL//本地调试使用system("pause");
#endifreturn 0;
}

不使用 string，而直接使用字符数组，处理速度能更快，我使用 string，只是为了调试方便而已。

时间复杂度

O(N)。

空间复杂度

O(N)。