Page 5 of 7

Posted: Fri Mar 24, 2006 4:08 am
by yiuyuho
Yes, I also found out that there exists other characters in the input.
My program handles all invalid input characters as if they are 'a' (of course not intentionally, only because it assumes that only valid characters occur).
Is that still true as of now? I guess we have to first change any non a-zA-Z to 'a' huh?

10679 WHY AC!!! I'm CRAZY!!!!!!!

Posted: Sat Mar 25, 2006 12:17 am
by tmdrbs6584
#include<iostream.h>
#include<string.h>
int main(){
char a[100001],b[100001];
int k,i,j,c,d;
cin >> c;
for(i=0;i<c;i++){
cin.get();
cin >> a;
cin >> d;
cin.get();
for(j=0;j<d;j++){
cin >> b;
int sw=0,len=strlen(a),z=0,len2=strlen(b);
for(k=0;;k++){
if(sw==len2)
break;
if(b[sw]==a[z]){
sw++;
z++;
}
else{
z++;
sw=0;
}
if(z==len2)
break;
}
if(sw==len2)
cout << "y" << endl;
else
cout << "n" << endl;
}
}
return 0;
}
THIS IS WHY AC?
IT'S WRONG!

Posted: Sat Mar 25, 2006 12:19 am
by tmdrbs6584
SEE MY CODE. IT's AC AND I'M GETTING CRAZY...
#include<iostream.h>
#include<string.h>
int main(){
char a[100001],b[100001];
int k,i,j,c,d;
cin >> c;
for(i=0;i<c;i++){
cin.get();
cin >> a;
cin >> d;
cin.get();
for(j=0;j<d;j++){
cin >> b;
int sw=0,len=strlen(a),z=0,len2=strlen(b);
for(k=0;;k++){
if(sw==len2)
break;
if(b[sw]==a[z]){
sw++;
z++;
}
else{
z++;
sw=0;
}
if(z==len2)
break;
}
if(sw==len2)
cout << "y" << endl;
else
cout << "n" << endl;
}
}
return 0;
}
THIS IS WHY AC?
IT'S WRONG!

Posted: Sat Mar 25, 2006 12:09 pm
by little joey
Just a few simple rules to keep the forums usable for everybody:
- use code tags, so it's easier for others to read your code;
- don't post accepted code;
- don't just dump your code, but explain your problem;
- don't post the same posting in more than one thread, it clutters the forum.

Posted: Sat Mar 25, 2006 10:53 pm
by yiuyuho
The test data is weak, my wrong program get AC too :O

Posted: Sun Mar 26, 2006 10:02 am
by tmdrbs6584
Thanks for your advice. I'll remember your advices in my heart every time from now.

10679 why TLE?

Posted: Tue Jul 04, 2006 2:42 pm
by Zakaria Alam

Code: Select all

//TLE
#include<stdio.h>
#include<string.h>

char S[100050],T[1050],*p,c;
long q,k,i,j;

void main()
{
	//what is the problem
	scanf("%ld",&k);//test case=k
	for(i=0;i<k;i++)
	{
		scanf(" %s",S);
		scanf(" %ld",&q);
		for(j = 0;j<q;j++)
		{
			scanf(" %s",T);
			p = strstr(S,T);
			if(p)
				printf("y\n");
			else
				printf("n\n");
		}
	}
}

Posted: Tue Jul 04, 2006 8:04 pm
by A1
wrong volume!
use the search option of this board to find info about this problem.

Posted: Fri Mar 30, 2007 10:02 am
by DJWS
I generate some test data although I haven't solved this problem.
The output should be all 'y'.
5
aaa
6
a
aa
aaa
a
aa
aaa
abc
6
a
b
c
ab
bc
abc
abcabab
6
aba
abc
bab
bca
cab
abab
aaabbb
6
ab
aabb
aaabbb
aabbb
abbb
bb
abbabba
6
ab
ba
abb
bba
abba
bbabb

Why WA

Posted: Sun Apr 22, 2007 11:25 pm
by Oyhama Hora
Why WA?
I dont know. Anybody can help me ?
thanks.

#include<iostream>
#include<string>
using namespace std;
main()
{
char frase[100000],text[1000];
string output;
int casos,x,query,y,stat;
output="";
cin>>casos;
stat=0;
for(x=1;x<=casos;x++)
{
cin>>frase;
cin>>query;
if(query<1000)
{

for(y=1;y<=query;y++)
{
cin>>text;
if(strstr(frase,text)&& frase[1]==text[1])
{

if(stat==0)
stat=1;

else
output+="\n";

output+="y";
}
else
{
if(stat==0)
stat=1;

else
output+="\n";

output+="n";
}

}

}

}

cout << output;

}

10679 WA

Posted: Mon May 14, 2007 2:44 pm
by sfelixjr
Hi guys,
i have made an easy code in java for this problem, but i got WA, does anybody have any test cases for it? Or find a problem with my code?
My code is here:

Code: Select all

import java.io.IOException;


class Main {
	static String ReadLn(int maxLg) // utility function to read from stdin
	{
		byte lin[] = new byte[maxLg];
		int lg = 0, car = -1;
		try {
			while (lg < maxLg) {
				car = System.in.read();
				if ((car < 0) || (car == ' ') || (car == '\n'))
					break;
				lin[lg++] += car;
			}
		} catch (IOException e) {
			return (null);
		}

		if ((car < 0) && (lg == 0))
			return (null); // eof
		return (new String(lin, 0, lg));
	}
	public static void main(String[] args) {
		Main d = new Main();
		d.begin();
	}
	void begin(){
		int num = Integer.parseInt(ReadLn(255));
		for (int i = 0;i<num;i++){
			String s = ReadLn(255);
			int q = Integer.parseInt(ReadLn(255));
			for (int j = 0;j<q;j++){
				String query = ReadLn(255);
				if (s.indexOf(query)>=0)
					System.out.println("y");
				else
					System.out.println("n");
			}
		}
	}
}

Posted: Mon May 14, 2007 6:57 pm
by yiuyuho
hmm....did you read the maximum length of the strings in the problem? :-P

Posted: Mon May 14, 2007 6:58 pm
by yiuyuho
actually, I dont use java on UVa, but you cant use BufferedReader for java submissions?

Posted: Sun Jul 29, 2007 8:22 pm
by Kallol
My KMP failed with TLE. So, whats the trick?? any optimization upon the KMP or any new algorithm . I found Krugel and Sajjad bhai suggested two different new algorithm . But The r not assymtotically faster than KMP. Infact according to Cormen, KMP is the optimal algorithm for String matching. Is there any critical input that just makes the KMP fool and passes for any other algo??

my code here :

Code: Select all

#include<cstdio>
#include<iostream>
#include<cstring>

#define KMP_PATTERN_MAX 10005

using namespace std;

int Failure[KMP_PATTERN_MAX];

void failure_function(char* P)
{
	register int m=strlen(P);

	Failure[0]=0;
	register int i=1;
	register int j=0;

	register int l=strlen(P);

	while(i<l)
	{
		if(P[i]==P[j])
		{
			Failure[i]=j+1;
			i++;
			j++;
		}
		else if(j>0)
		{
			j=Failure[j-1];
		}
		else
		{
			Failure[i]=0;
			i=i+1;
		}
	}
	return;
}


int KMP_MATCH(char* T, char* P)
{
	register int n=strlen(T);
	register int m=strlen(P);

	failure_function(P);
	
	

	int i=0,j=0;
	while(i<n)
	{
		if(P[j]==T[i])
		{
			if(j==(m-1))
			{
				return (i-j);
			}
			i++;
			j++;
		}
		else if(j>0)
		{
			j=Failure[j-1];
		}
		else
		{
			i++;
		}
	}
	
	return -1;
}



int main(void)
{

	char T[100009],P[1009];
	register int t,n;
	scanf("%d",&t);

	while(t--)
	{
		scanf("%s",&T);
		scanf("%d",&n);
		while(n--)
		{
			scanf("%s",&P);
			if(KMP_MATCH(T,P)>=0)
			{
				printf("y\n");
			}
			else
			{
				printf("n\n");
			}
		}
	}
	return 0;
}

TLE 10679 - I love Strings!!!

Posted: Wed Sep 03, 2008 8:50 am
by newton
Hmm i think this problem cant be solved by KMP.