OJ Board

Why WA in 10340?!

My code:

[c]#include <stdio.h>
#include <string.h>

int main()
{
char s1[10002], s2[10002];
int size_s1, size_s2, cont, i;

while(scanf("%s %s", s1, s2) != EOF){
size_s1 = strlen(s1);
size_s2 = strlen(s2);
cont=0;
for(i=0; i < size_s2; ++i){
if(cont < size_s1)
if(s2 == s1[cont]){
cont++;
}
}
if(cont == size_s1)
printf("Yes\n");
else
printf("No\n");
}

return 0;
}
[/c]

use 1000000 as array size.

Thank you my friend! Acc!

This seems to be an easy problem but I can't figure out why my code doesn't work
maybe there is some special case that I haven't think it.
here is my code:

[c]
#include <stdio.h>
#include <string.h>

int main()
{
char s[150],t[150];
int i,j;
int temp;
while(scanf("%s %s",&s,&t)!=EOF)
{
temp=0;
j=0;
for(i=0;i<=strlen(s)-1;i++)
for (;j<=strlen(t)-1;j++)
if (s==t[j])
{
temp++;
break;
}
if (temp==strlen(s))
printf("Yes\n");
else
printf("No\n");
}
return 0;
}[/c]

thx for reading!

I read a lot about 10340, written in this forum
I use char of 1000000, I use long.
My program is clear. But I can't find a mistake
Help me, please!
I do not want to use two char arrays of size 1000000,
I use only one. So I use getchar().
I use scanf("\n") to pass eoln symbol. It works right.

Help! Why WA????

#include <stdio.h>
char line[1000000];

int main(void)
{
long i,len;
char c;
while (!feof(stdin))
{
len = 0;
while ((c = getchar())!= ' ') line[len++] = c;
i = 0;
while ((c = getchar())!= '\n')
if (c == line[i]) i++;
if (i == len) printf("Yes\n");
else printf("No\n");
scanf("\n");
}
return 0;
}

Try the input
ab ab
a ab

Your output is
Yes
No

Try the two test cases in this order! I think you can guess what is wrong.

I don't understand why i got WA
can somebody give me a set of inputs..?
thanks a lot

Your code is OK..

The problem its your array size .. put one more zero on MAX.

YES YOUR CODE IS OK BUT FOR THE ARRAY SIZE....
I GET ACC BY 100000 SIZE OF ARRAY TRY IT

GOOD LUCK

YA...! I got AC now.
thanks for your help

I am just wondering what is the best
algorithm for solving this problem.

I do the following:

1) I take the two strings and name them strX and strY.
Let's denote their lengths by LenX and LenY respectively.

2) I calculate the length N of the
Longest Common Subsequence ( LCS ) of strX and strY.

3) Then I check if N is equal to the length of the first
string strX. If so, I print "Yes", otherwise I print "No".

Roughly speaking the algorithm I've implemented for finding the
length of the LCS of strX and strY uses O(LenX+LenY) memory and
spends O(LenX*LenY) running time. Here LenX and LenY and the lengths
of strX and strY respectively.

Can the running time complexity be improved ?
Memory concerns me less for the moment.

Apparently my algorithm does too much.

For that problem I saw a lot of people getting ACC with
running time under 0.010 sec.
My running time is about 0.500 sec.

So apparently there's some much more efficient algotihm
for solving this one. Any hints about it ?

Apparently my algorithm does too much.

For that problem I saw a lot of people getting ACC with
running time under 0.010 sec.
My running time is about 0.500 sec.

So apparently there's some much more efficient algotihm
for solving this one. Any hints about it ?

Note that only 0's and 1's appear, so you can preprocess the array for queries in some way..

Sedefcho wrote:Apparently my algorithm does too much.

I think so, too. Note that you only need to find the presence of a subsequence not the length of the LCS. My [len (X) * len (Y)] brute force solution times 0.008 sec.