10679 - I Love Strings!!

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Re: 10679 - I love Strings!!!

Post by DJWS » Wed Sep 03, 2008 9:40 am

Because your algorithm is not efficient enough. Try another better algorithm.
newton wrote: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;
}
Last edited by DJWS on Wed Sep 10, 2008 3:46 pm, edited 1 time in total.

kantaki
New poster
Posts: 10
Joined: Tue May 29, 2007 6:18 pm

Re: 10679 - I love Strings!!!

Post by kantaki » Sun Sep 07, 2008 9:28 am

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 10679 - I love Strings!!!

Post by Jan » Sun Sep 07, 2008 10:30 am

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

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

Re: 10679 - I love Strings!!!

Post by ptargino » Sat Nov 08, 2008 8:33 pm

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. :D

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Re: 10679 - I love Strings!!!

Post by DJWS » Tue Nov 11, 2008 7:20 am

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. :D
The prefix of one string is also the substring of one string. It is reasonable that we need to check all the prefixes.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 10679 - I love Strings!!!

Post by Obaida » Mon Feb 23, 2009 11:06 am

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

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.

Moshiur Rahman
New poster
Posts: 13
Joined: Mon Sep 08, 2008 6:57 pm
Location: State University of Bangladesh

Re: 10679 - I love Strings!!!

Post by Moshiur Rahman » Thu Mar 26, 2009 4:44 pm

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

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

Re: 10679 - I love Strings!!!

Post by cytmike » Sun Apr 19, 2009 5:35 am

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. :D
I can confirm this. Dont bother with KMP, suffix tree or whatsoever.
Impossible is Nothing.

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

Re: 10679 - I love Strings!!!

Post by victro_hugo » Mon May 17, 2010 12:49 am

Yeap is just the prefix

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

Re: 10679 - I love Strings!!!

Post by DD » Fri Mar 25, 2011 5:02 am

I solved this problem by using Aho-Corasick Algorithm. I just wonder why some results are 0.10 :o
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.

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

Re: 10679 - I love Strings!!!

Post by K0stIa » Thu Aug 11, 2011 10:11 pm

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
New poster
Posts: 3
Joined: Wed Aug 25, 2010 4:57 pm

Insufficient test data for 10679 - I Love Strings!!

Post by xander7b » Tue Jul 24, 2012 3:46 pm

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
New poster
Posts: 16
Joined: Fri May 17, 2013 8:59 am

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

Post by ashdboss » Fri May 17, 2013 9:08 am

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

hello
New poster
Posts: 25
Joined: Sun Mar 10, 2013 7:29 pm

Re: 10679 - I love Strings!!!

Post by hello » Mon Jun 24, 2013 6:13 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10679 - I love Strings!!!

Post by brianfry713 » Tue Jun 25, 2013 10:38 pm

Try a different problem.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 106 (10600-10699)”