10679 - I Love Strings!!

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Fri Mar 24, 2006 4:08 am

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?

User avatar
tmdrbs6584
Learning poster
Posts: 98
Joined: Sat Jan 21, 2006 12:45 pm
Location: Busan,Corea(Republic of)

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

Post by tmdrbs6584 » Sat Mar 25, 2006 12:17 am

#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!

User avatar
tmdrbs6584
Learning poster
Posts: 98
Joined: Sat Jan 21, 2006 12:45 pm
Location: Busan,Corea(Republic of)

Post by tmdrbs6584 » Sat Mar 25, 2006 12:19 am

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!

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sat Mar 25, 2006 12:09 pm

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.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Sat Mar 25, 2006 10:53 pm

The test data is weak, my wrong program get AC too :O

User avatar
tmdrbs6584
Learning poster
Posts: 98
Joined: Sat Jan 21, 2006 12:45 pm
Location: Busan,Corea(Republic of)

Post by tmdrbs6584 » Sun Mar 26, 2006 10:02 am

Thanks for your advice. I'll remember your advices in my heart every time from now.

Zakaria Alam
New poster
Posts: 2
Joined: Tue Jul 04, 2006 2:28 pm
Location: CSE-SUST-Bangladesh

10679 why TLE?

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

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");
		}
	}
}
zakaria

User avatar
A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by A1 » Tue Jul 04, 2006 8:04 pm

wrong volume!
use the search option of this board to find info about this problem.

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Post by DJWS » Fri Mar 30, 2007 10:02 am

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

Oyhama Hora
New poster
Posts: 3
Joined: Tue May 24, 2005 10:58 pm

Why WA

Post by Oyhama Hora » Sun Apr 22, 2007 11:25 pm

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;

}

sfelixjr
New poster
Posts: 9
Joined: Wed Apr 25, 2007 3:29 pm
Location: Brazil
Contact:

10679 WA

Post by sfelixjr » Mon May 14, 2007 2:44 pm

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");
			}
		}
	}
}

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Mon May 14, 2007 6:57 pm

hmm....did you read the maximum length of the strings in the problem? :-P

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Mon May 14, 2007 6:58 pm

actually, I dont use java on UVa, but you cant use BufferedReader for java submissions?

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Sun Jul 29, 2007 8:22 pm

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;
}
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

TLE 10679 - I love Strings!!!

Post by newton » Wed Sep 03, 2008 8:50 am

Hmm i think this problem cant be solved by KMP.
Last edited by newton on Sun Sep 07, 2008 1:07 pm, edited 1 time in total.

Post Reply

Return to “Volume 106 (10600-10699)”