## 10679 - I love Strings!!!

Moderator: Board moderators

### Re: 10679 - I love Strings!!!

This problem cant be solved with KMP. You have to make suffix tree to solve this problem.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

### Re: 10679 - I love Strings!!!

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.
ptargino
New poster

Posts: 2
Joined: Sat Nov 08, 2008 8:30 pm

### Re: 10679 - I love Strings!!!

ptargino wrote: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.
DJWS
Learning poster

Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan

### Re: 10679 - I love Strings!!!

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;}`
try_try_try_try_&&&_try@try.com
This may be the address of success.
Obaida
A great helper

Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 10679 - I love Strings!!!

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
Never think too hard, let ideas come to you...
Moshiur Rahman
New poster

Posts: 13
Joined: Mon Sep 08, 2008 6:57 pm

### Re: 10679 - I love Strings!!!

ptargino wrote: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.
Impossible is Nothing.

cytmike
Learning poster

Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States

### Re: 10679 - I love Strings!!!

Yeap is just the prefix
victro_hugo
New poster

Posts: 2
Joined: Mon Apr 12, 2010 5:51 pm

### Re: 10679 - I love Strings!!!

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

Wanted to work at best companies?
Struggled with interview problems that could be solved in 15 minutes?
Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.
DD
Experienced poster

Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California

### Re: 10679 - I love Strings!!!

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

1
abcAGbcbd
3
bcA
abcAG
cA

n
n
n

y
y
y.

K0stIa
New poster

Posts: 4
Joined: Thu Sep 23, 2010 10:20 pm

### 10679 - I love Strings!!! submission error !!!

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

Posts: 2
Joined: Fri May 17, 2013 8:59 am

Previous