10679 - I Love Strings!!

[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?

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

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

[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.

[yiuyuho]

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

[tmdrbs6584]

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

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

[A1]

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

[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

[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;

}

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

[yiuyuho]

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

[yiuyuho]

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

[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;
}

[newton]

Hmm i think this problem cant be solved by KMP.