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.

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

[DJWS]

Because your algorithm is not efficient enough. Try another better algorithm.

whay TLE, im just comparing upto substring lenth?

Code: Select all

#include <cstdio>
#include <algorithm>

using namespace std;

int main(){
   freopen("in.txt","rt",stdin);
   int Case,subNum,i;
   char S1[100001],*p;
   char S2[1001];
   char S3[1001];
   int N1,N2;
   scanf("%d",&Case);
   while(Case--){     
      scanf("%s",S1);
      scanf("%d",&subNum);
      N1 = strlen(S1);
      while(subNum--){         
         scanf("%s",S2);         
         N2 = strlen(S2);
         bool f = false;
         for(i = 0; S2[i]; i++)
            if(S1[i] == S2[i])
            {
            }
            else{
               f = true;   
               break;               
            }                       
            if(!f)
               printf("y\n");
            else
               printf("n\n");
      }
   }   
   return 0;
}


[kantaki]

I got TLE.
I used KMP Algorithm, I think.

I think that this problem's solution is KMP Algorithm, isn't it?
What is my problem with my code?

Here is my code.
please help me...

Code: Select all

#include <stdio.h>
#define MAX 1000000

int FailureFunction[MAX];
char Text[MAX];
char Pattern[MAX];


void KMPFailureFunction() {
   int length;
   int i, j;
   length = strlen(Pattern);
   i = 1;
   j = 0;
   while(i < length) {
      if(Pattern[j] == Pattern[i]) {
         FailureFunction[i] = j+1;
         i++;
         j++;
      }
      else if(j>0) j=FailureFunction[j-1];
      else {
         FailureFunction[i] = 0;
         i++;
      }
   }
}


int KMPMatch() {
   int i, j, text_length, pattern_length;

   KMPFailureFunction();
   text_length = strlen(Text);
   pattern_length = strlen(Pattern);
   i = j = 0;
   while(i<text_length) {
      if(Pattern[j] == Text[i]) {
         i++;
         j++;
         if(j==pattern_length) return 1;
      }
      else if(j>0) j = FailureFunction[j-1];
      else i++;
   }
   return 0;
}


int main() {
   int rep;
   int pat_num;

   scanf("%d\n", &rep);
   while(rep--) {
      scanf("%s\n", Text);
      scanf("%d\n", &pat_num);
      while(pat_num--) {
         scanf("%s", Pattern);

         if(KMPMatch()) printf("y\n");
         else printf("n\n");
      }
   }

   return 0;
}