Loại bỏ one và two

Đề bài

Mô tả

Cho một xâu s=s1s2sn khác rỗng, chỉ gồm các chữ cái Latin thường.

Một xâu bị xem là "xấu" nếu nó chứa ít nhất một trong hai xâu con "one" hoặc "two". Nói cách khác, s là xâu xấu nếu tồn tại chỉ số j (1jn2) sao cho sjsj+1sj+2= "one" hoặc sjsj+1sj+2= "two".

Bạn được phép chọn một tập các vị trí và xoá đồng thời tất cả các chữ cái tại những vị trí đó. Ví dụ, với s= "onetwone", nếu chọn hai vị trí 36 thì kết quả còn lại là "ontwne".

Hãy tìm số vị trí ít nhất cần xoá để xâu s không còn là xâu xấu, và chỉ ra các vị trí đó.

Dữ liệu vào

  • Dòng đầu chứa số nguyên t - số lượng bộ dữ liệu.
  • Mỗi bộ dữ liệu gồm một dòng chứa xâu s khác rỗng, chỉ gồm chữ cái Latin thường.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra:

  • Dòng đầu chứa số nguyên r (0r|s|) - số vị trí ít nhất cần xoá.
  • Dòng thứ hai chứa r số nguyên phân biệt - các vị trí cần xoá (theo thứ tự bất kỳ), đánh số từ 1 đến |s|. Nếu r=0 thì dòng này có thể để trống.

Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ràng buộc

  • 1t104
  • 1|s|1.5·105
  • Tổng độ dài của tất cả các xâu không vượt quá 1.5·106.

Ví dụ

Input Output Giải thích
4
onetwone
testme
oneoneone
twotwo
2
2 6
0

3
2 5 8
2
2 5
"onetwone" chứa "two" và "one" đan nhau ở chữ o; xoá 2 vị trí là đủ. "testme" đã tốt nên r=0. "oneoneone" cần xoá 3 chữ. "twotwo" cần xoá 2 chữ. Đây chỉ là một trong nhiều đáp án hợp lệ.
4
two
one
twone
abc
1
2
1
2
1
3
0
Với "twone", hai xâu con "two" và "one" dùng chung chữ o ở vị trí 3, nên chỉ cần xoá đúng vị trí 3 là loại được cả hai. "abc" không cần xoá.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0