10679 - I Love Strings!!

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

[Jan]

This problem cant be solved with KMP. You have to make suffix tree to solve this problem.

[ptargino]

The test cases of this problems are wrong. Actually, you just need to verify if each substring is prefix of the original. I've done this way and got AC.

[DJWS]

The test cases of this problems are wrong. Actually, you just need to verify if each substring is prefix of the original. I've done this way and got AC.

The prefix of one string is also the substring of one string. It is reasonable that we need to check all the prefixes.

[Obaida]

I know KMP and tried to implement it in the program. But got WA.

Code: Select all

#include<stdio.h>
#include<string.h>
int pi[100001],len_st,len_t;
char st[100001],t[1001];
void prefix_function()
{
	int k=0,i;
	pi[0]=0;
	for(i=1;i<len_t;i++)
	{
		while(k>0&&t[k]!=t[i])
			k = pi[k];
		if(t[k]==t[i])
			k++;
		pi[i] = k;
	}
}
int main()
{
	bool found;
	int i,n,c,j;
	scanf("%d%*c",&n);
	while(n--)
	{
		gets(st);
		len_st = strlen(st);
		scanf("%d%*c",&c);
		while(c--)
		{
			gets(t);
			len_t = strlen(t);
			prefix_function();
			j=0;found=0;
			for(i=0;i<len_st;i++)
			{
				while(j>0&&t[j]!=st[i])
					j = pi[j];
				if(t[j]==st[i])
					j++;
				if(j==len_t-1){found = 1; break;}
			}
			if(found)puts("y");
			else puts("n");
		}
	}
	return 0;
}

[Moshiur Rahman]

You can't get AC with KMP in this problem! Actually you don't need KMP
Fortunately ( or unfortunately ) the judge data is wrong and funny ( sorry to say that )
You can get AC just by checking whether t is a prefix of st or not!

Just check the first strlen(t) characters of st.

By the way, your implementation of prefix_function() is not correct. The correct one should be:

Code: Select all

void prefix_function()
{
     int k = -1,i;
     pi[0] = -1;
     for(i = 1; i < len_t; i++)
     {
         while(k > -1 && t[k+1] != t[i])
             k = pi[k];
          if(t[k+1]==t[i])
             k++;
          pi[i] = k;
     }
}

Then, I think you will have to change your matching method too! Check the following :

Code: Select all

bool KMP_match(char txt[], chat pattern[])     // we search for "pattern" in "txt"
{
    int i = 0, j = 0;               // i - index of "txt" , j - index of "pattern"

    int tlen = strlen(txt), plen = strlen(pattern);

    while(1)
    {
       if(i==tlen) break;
       if(txt[i]==pattern[j])
       {
           ++i;
           ++j;
       }
       else if(j > 0)
       {
            j = pi[j-1] + 1;
       }
       else
           ++i;
       if(j==plen)
           return true;    // we have found a successful match :)  
    }
    return false;          // no match!!
}

hope I didn't make any silly mistake

[cytmike]

The test cases of this problems are wrong. Actually, you just need to verify if each substring is prefix of the original. I've done this way and got AC.

I can confirm this. Dont bother with KMP, suffix tree or whatsoever.

[victro_hugo]

Yeap is just the prefix

[DD]

I solved this problem by using Aho-Corasick Algorithm. I just wonder why some results are 0.10

[K0stIa]

Who can explain me why the server gives on the following test

1
abcAGbcbd
3
bcA
abcAG
cA

the answer
n
n
n

instead of
y
y
y.

Thnx in advance.

[xander7b]

Test cases are not sufficient.

A buggy code got AC, yet it fails this simple case:
1
taken
4
taken
take
ake
ke

returns y,n,y,y instead of y,y,y,y

Buggy AC code: http://ideone.com/Tblbi

[ashdboss]

Can u please tell me why SE is resulting for 10679 ? Is it a coding related problem ?

[hello]

Code: Select all

#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#define LLU long long unsigned int
#define LLD long long double
#define FOR(i,N) for(int i=0;i<(N);i++)
#define Vec vector<int>
#define Vit vector<int>::iterator

using namespace std;

int boyer_moore(char* sstr, char* pattern)

{

    char* inits = sstr;

    char* initp = pattern;



    int spatt = strlen(pattern);

    while(*pattern != '\0') pattern++;

    // this algorithm tested for printable ASCII characters

    // from ASCII, 65-90 and 97-122

    int* jump_table=(int*) calloc(128, sizeof(int));

    int count=0;



    while(pattern != initp) {

        pattern--;

        jump_table[*pattern]=count;

        count++;

    }



    char* stmp=0;

    char* iter=0;

    int shift=0;

    int bad_count=0;

    int bcount=0;

    while(*sstr != '\0')

    {

        bcount=0;

        bad_count=spatt;

        stmp = sstr+ (spatt-1);

        iter = pattern + (spatt-1);

        while(*stmp == *iter) {

            bad_count--;

            bcount++;

            stmp--;

            iter--;

            if(bcount==spatt)

                return sstr-inits;

        }



        //jump table

        if(jump_table[*stmp] == 0) {

            // the character not found in pattern

            shift=bad_count;

        } else {

            shift=jump_table[*stmp];

            (shift - bcount < 1)?shift = 1: shift = shift-bcount;

        }

        sstr += shift;

    }

    //not found

    return -1;

}







int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);

   int cases;
   cin>>cases;
getchar();
   while(cases--){

   char str[1000000];
   gets(str);
   int num;
   cin>>num;
    getchar();
   while(num--){

   char searc[1000000];
   gets(searc);
   int l=boyer_moore(str, searc);
if(l==-1)cout<<"n"<<endl;
else cout<<"y"<<endl;
   }
   }
    return 0;
}

why SE.....?

[brianfry713]

Try a different problem.