Codeforces #208 div2前两题及思维风暴(二)
word. A heart is a sequence of two characters: the "less" characters (<) and the digit three (3). After applying the code, a test message looks like that: <3word1<3word2<3 ... wordn<3.
Encoding doesn't end here. Then Dima inserts a random number of small English characters, digits, signs "more" and "less" into any places of the message.
Inna knows Dima perfectly well, so she knows what phrase Dima is going to send her beforehand. Inna has just got a text message. Help her find out if Dima encoded the message correctly. In other words, find out if a text message could have been received by encoding in the manner that is described above.
Input
The first line contains integer n (1 ≤ n ≤ 105) — the number of words in Dima's message. Next n lines contain non-empty words, one word per line. The words only consist of small English letters. The total length of all words doesn't exceed 105.
The last line contains non-empty text message that Inna has got. The number of characters in the text message doesn't exceed 105. A text message can contain only small English letters, digits and signs more and less.
Output
In a single line, print "yes" (without the quotes), if Dima decoded the text message correctly, and "no" (without the quotes) otherwise.
Sample test(s)
input
3
i
love
you
<3i<3love<23you<3
output
yes
input
7
i
am
not
main
in
the
family
<3i<>3am<3the<3<3family<3
output
no
Note
Please note that Dima got a good old kick in the pants for the second sample from the statement.
这个题目如果看懂的话，相当easy，关键是要看懂。。当时第一题没搞出来就直接没看了。前面给你n个串，在每个串前面加上<3后面加上>3链接在一起。最后在链接好的串里插入任意字段。再给你一个串，问满足条件否？
开始原先想的就是先比较<3然后跟串一个一个挨着比较，每比较完一个，就再匹配一个<3。具体实现见代码。最后还需要匹配一个<3.
代码：
[cpp]
#include
#include
#include
#include
#include
#include
using namespace std;
string a[100005];
string p;
int main()
{
int n,i,j;
while(cin>>n)
{
for(i=0;i
cin>>a[i];
cin>>p;
int flag=0;
int fla=0;
int s=0,t=0;
for(i=0;i
{
if(s==n)
{
fla=1;
break;
}
if(flag==0) //先匹配<
{
if(p[i]=='<')
flag=1;
}
else if(flag==1) //匹配3
{
if(p[i]=='3')
flag=2;
}
else
{
if(p[i]==a[s][t]&&t==a[s].length()-1)
{
s++;
t=0;
flag=0; //匹配一个串后需要重新匹配<3
}
else if(p[i]==a[s][t])
{
t++;
}
}
}
//cout<
flag=0;
if(fla) //匹配最后的<3
{
for(j=i;j
{
if(flag==0) //匹配<
{
if(p[j]=='<')
flag=1;
j++;
}
else if(flag==1) //匹配3
{
if(p[j]=='3')
{
fla=2;
break;
}
j++;
}
}
}
if(fla==2) puts("yes");
else puts("no");
}
return 0;
}
/*
3
i
love
you