10679 - I love Strings!!!

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

[ashdboss]

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