Did you mean…
题面翻译
都是小写字母。
给你一个字符串,如果它的子串同时满足
1、三个或以上个连着的辅音字母
2、这一段连着的辅音字母不是全部一样的
就认为它不合法
现在要求用最少的空格隔开这个字符串,使得它变成合法的。
题目描述
Beroffice text editor has a wide range of features that help working with text. One of the features is an automatic search for typos and suggestions of how to fix them.
Beroffice works only with small English letters (i.e. with 26 letters from a to z). Beroffice thinks that a word is typed with a typo if there are three or more consonants in a row in the word. The only exception is that if the block of consonants has all letters the same, then this block (even if its length is greater than three) is not considered a typo. Formally, a word is typed with a typo if there is a block of not less that three consonants in a row, and there are at least two different letters in this block.
For example:
- the following words have typos: “hellno”, “hackcerrs” and “backtothefutttture”;
- the following words don’t have typos: “helllllooooo”, “tobeornottobe” and “oooooo”.
When Beroffice editor finds a word with a typo, it inserts as little as possible number of spaces in this word (dividing it into several words) in such a way that each of the resulting words is typed without any typos.
Implement this feature of Beroffice editor. Consider the following letters as the only vowels: ‘a’, ‘e’, ‘i’, ‘o’ and ‘u’. All the other letters are consonants in this problem.
输入格式
The only line contains a non-empty word consisting of small English letters. The length of the word is between $ 1 $ and $ 3000 $ letters.
输出格式
Print the given word without any changes if there are no typos.
If there is at least one typo in the word, insert the minimum number of spaces into the word so that each of the resulting words doesn’t have any typos. If there are multiple solutions, print any of them.
样例输入 #1
hellno
样例输出 #1
hell no
样例输入 #2
abacaba
样例输出 #2
abacaba
样例输入 #3
asdfasdf
样例输出 #3
asd fasd f
算法1
(模拟) $O(n^2)$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
string s;
int cnt;
bool check(char ch) {
int a[]= {'a','e','i','o','u'}; //5个元音字母
// cout<<"ch= "<<ch<<endl;
for(int i=0; i<5; i++) {
if(ch==a[i])
return 1;
}
return 0;
}
int main() {
cin>>s;
for(unsigned int i=0; i<s.size(); i++) {
//判断是什么字母
if(check(s[i])) //如果是元音字母
cnt=0; //清零
else {
cnt++;
//判断是否是连续且三个不同的辅音字母
if(cnt>=3 && !(s[i]==s[i-1]&&s[i]==s[i-2])) {
cout<<" ";
// cout<<"s[i]="<<s[i]<<",s[i-1]="<<s[i-1]<<",s[i-2]="<<s[i-2]<<endl;
//!!! 前两个辅音字母"空格"后一个辅音字母
cnt=1; //不要忘记后一个辅音字母
}
}
// cout<<endl<<"cnt="<<cnt<<endl;
cout<<s[i];
}
return 0;
}