Codeforces Round #568 (Div. 2 B - Email from Polycarp

B - Email from Polycarp Methodius received an email from his friend Polycarp. However, Polycarp’s keyboard is broken, so pressing a key on it once may cause the corresponding symbol to appear more than once (if you press a key on a regular keyboard, it prints exactly one symbol).
For example, as a result of typing the word “hello”, the following words could be printed: “hello”, “hhhhello”, “hheeeellllooo”, but the following could not be printed: “hell”, “helo”, “hhllllooo”.
Note, that when you press a key, the corresponding symbol must appear (possibly, more than once). The keyboard is broken in a random manner, it means that pressing the same key you can get the different number of letters in the result.
For each word in the letter, Methodius has guessed what word Polycarp actually wanted to write, but he is not sure about it, so he asks you to help him.
You are given a list of pairs of words. For each pair, determine if the second word could be printed by typing the first one on Polycarp’s keyboard.
Input The first line of the input contains one integer ? (1≤?≤105) — the number of pairs to check. Further input contains ? descriptions of pairs.
The first line of each description contains a single non-empty word ? consisting of lowercase Latin letters. The second line of the description contains a single non-empty word ? consisting of lowercase Latin letters. The lengths of both strings are not greater than 106.
It is guaranteed that the total length of all words ? in the input is not greater than 106. Also, it is guaranteed that the total length of all words ? in the input is not greater than 106.
Output Output ? lines. In the ?-th line for the ?-th pair of words ? and ? print YES if the word ? could be printed by typing the word ?. Otherwise, print NO.
Examples inputCopy 4 hello hello hello helloo hello hlllloo hello helo outputCopy YES YES NO NO inputCopy 5 aa bb codeforces codeforce polycarp poolycarpp aaaa aaaab abcdefghijklmnopqrstuvwxyz zabcdefghijklmnopqrstuvwxyz outputCopy NO NO YES NO NO
제목:https://codeforces.com/contest/1185/problem/B제목: 어떤 키를 눌렀을 때 상응하는 기호가 나타나야 합니다. (한 번이 아닐 수도 있습니다.)키보드가 무작위로 끊겼다는 것은 같은 키를 누르면 결과에서 서로 다른 자모를 얻을 수 있다는 것을 의미한다.두 번째 문자열은 먼저 첫 번째 문자열보다 길다는 것을 설명한다. 두 문자열을 비교하면 바늘로 생각하면 첫 번째는 a 문자열이고 두 번째는 b 문자열이다. 만약에 a, b 요소가 같으면 바늘++로 다음 요소를 가리킨다.만약 a, b의 요소가 다르지만, b 문자열에 인접한 문자가 같으면 이어서 실행하고, 그렇지 않으면 바로 튀어나옵니다.AC 코드:
#include< iostream>
#include< cstdio>
#include< cstring>
#include< algorithm>
#define rep(i,a,b)for(int i=a;i<=b;i++)
using namespace std;
const int maxn=1e6+5;
char a[maxn],b[maxn];
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        scanf("%s%s",a,b);
        int len=strlen(b);
        int pos=0;
        int flag=1;
        rep(i,0,len-1){
            if(b[i]==a[pos]){
                pos++;
                //printf("%d
",pos);
} else{ if(i>0&&b[i]==b[i-1])continue;// b[i+1]==b[i] else{ flag=0; break; } } } if(pos!=strlen(a))flag=0; if(flag)printf("YES
"
); else printf("NO
"
); } return 0; }

좋은 웹페이지 즐겨찾기