## 10679 - I Love Strings!!

Moderator: Board moderators

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

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

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

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.

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
Contact:

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

ptargino
New poster
Posts: 2
Joined: Sat Nov 08, 2008 8:30 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.

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

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

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

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

Moshiur Rahman
New poster
Posts: 13
Joined: Mon Sep 08, 2008 6:57 pm

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

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

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.

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

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

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

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.

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

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

xander7b
New poster
Posts: 3
Joined: Wed Aug 25, 2010 4:57 pm

### Insufficient test data for 10679 - I Love Strings!!

Test cases are not sufficient.

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

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

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

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 bcount=0;

while(*sstr != '\0')

{

bcount=0;

stmp = sstr+ (spatt-1);

iter = pattern + (spatt-1);

while(*stmp == *iter) {

bcount++;

stmp--;

iter--;

if(bcount==spatt)

return sstr-inits;

}

//jump table

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

} else {

shift=jump_table[*stmp];

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

}

sstr += shift;

}

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

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