题目描述

难度分:$1400$

输入$T(\leq 10^4)$表示$T$组数据。所有数据字符串长度之和$≤1.5 \times 10^6$。

每组数据输入一个长度$\leq 1.5 \times 10^5$的字符串$s$，只包含小写字母。

删除尽量少的字符，使得字符串中不存在任何连续子串为$one$或$two$。

输出：第一行为删除的字符个数。第二行为删除的字符下标（下标从$1$开始）。

输入样例$1$

4
onetwone
testme
oneoneone
twotwo

输出样例$1$

2
6 3
0

3
4 1 7 
2
1 4

输入样例$2$

10
onetwonetwooneooonetwooo
two
one
twooooo
ttttwo
ttwwoo
ooone
onnne
oneeeee
oneeeeeeetwooooo

输出样例$2$

6
18 11 12 1 6 21 
1
1 
1
3 
1
2 
1
6 
0

1
4 
0

1
1 
2
1 11 

算法

贪心

感觉这样的题没有什么很好的办法，就是看逻辑是否严密的业务问题。发现two和one接龙形成twone的时候，去掉中间的o比较划算；其余情况下去掉one和two中间的特色字母比较划算。

因此可以先杜绝twone的出现，遍历$s$串，把要保留的索引放入$pos$数组，要删除的索引放入$del$数组；然后再考虑其他情况，遍历$pos$数组，将要保留的索引放入$pos_2$数组，一旦发现当前字母$s[i]$和$pos_2$中的后两位索引可以组成one或two，就把中间特色字母的索引去掉。

复杂度分析

时间复杂度

相当于遍历了两遍字符串，时间复杂度为$O(n)$。

空间复杂度

开辟了两个存索引的数组$pos$、$pos_2$以及一个$del$数组存储要删除的索引，三者的规模都是$O(n)$，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1500010;
char s[N];

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%s", s + 1);
        int n = strlen(s + 1);
        vector<int> pos, del;
        for(int i = 1; i <= n;) {
            if(i + 4 <= n && s[i] == 't' && s[i + 1] == 'w' && s[i + 2] == 'o' && s[i + 3] == 'n' && s[i + 4] == 'e') {
                pos.push_back(i);
                pos.push_back(i + 1);
                del.push_back(i + 2);
                pos.push_back(i + 3);
                pos.push_back(i + 4);
                i += 5;
            }else {
                pos.push_back(i);
                i++;
            }
        }
        vector<int> pos2;
        for(int i: pos) {
            int len = pos2.size();
            if(len < 2) {
                pos2.push_back(i);
            }else {
                if(s[i] == 'e' && s[pos2[len - 1]] == 'n' && s[pos2[len - 2]] == 'o') {
                    del.push_back(pos2[len - 1]);
                    pos2.pop_back();
                    pos2.push_back(i);
                }else if(s[i] == 'o' && s[pos2[len - 1]] == 'w' && s[pos2[len - 2]] == 't') {
                    del.push_back(pos2[len - 1]);
                    pos2.pop_back();
                    pos2.push_back(i);
                }else {
                    pos2.push_back(i);
                }
            }
        }
        int len = del.size();
        printf("%d\n", len);
        for(int x: del) printf("%d ", x);
        puts("");
    }
    return 0;
}