NHAY is a SPOJ question involving pattern search.↵
The Link:↵
http://www.spoj.com/problems/NHAY/↵
↵
My solution gives me TLE. Here is my code:↵
↵
↵
#include<bits/stdc++.h>↵
using namespace std;↵
int lps[500000];↵
char str[500000],str1[500000];↵
int main(){↵
int x,i,j;↵
while(scanf("%d",&x)!=EOF){↵
scanf("%s",str);↵
scanf("%s",str1);↵
lps[0]=0;↵
i=1;↵
j=0;↵
while(i<strlen(str)){↵
if(str[i]==str[j]){↵
lps[i]=j+1;↵
i++;↵
j++;↵
}↵
else if(j==0){↵
lps[i]=0;↵
i++;↵
}↵
else↵
j=lps[j-1];↵
}↵
i=j=0;↵
/*for(int i=0;i<strlen(str);i++)↵
printf("%d ",lps[i]);*/↵
while(i<strlen(str1)){↵
if(str1[i]==str[j]){↵
i++;↵
j++;↵
}↵
else if(j!=0)↵
j=lps[j-1];↵
else↵
i++;↵
if(j==strlen(str)){↵
printf("%d\n",(i-j));↵
j=lps[j-1];↵
}↵
}↵
printf("\n");↵
}↵
return 0;↵
}↵
What are some optimizations that I can apply on my code?
The Link:↵
http://www.spoj.com/problems/NHAY/↵
↵
My solution gives me TLE. Here is my code:↵
↵
↵
#include<bits/stdc++.h>↵
using namespace std;↵
int lps[500000];↵
char str[500000],str1[500000];↵
int main(){↵
int x,i,j;↵
while(scanf("%d",&x)!=EOF){↵
scanf("%s",str);↵
scanf("%s",str1);↵
lps[0]=0;↵
i=1;↵
j=0;↵
while(i<strlen(str)){↵
if(str[i]==str[j]){↵
lps[i]=j+1;↵
i++;↵
j++;↵
}↵
else if(j==0){↵
lps[i]=0;↵
i++;↵
}↵
else↵
j=lps[j-1];↵
}↵
i=j=0;↵
/*for(int i=0;i<strlen(str);i++)↵
printf("%d ",lps[i]);*/↵
while(i<strlen(str1)){↵
if(str1[i]==str[j]){↵
i++;↵
j++;↵
}↵
else if(j!=0)↵
j=lps[j-1];↵
else↵
i++;↵
if(j==strlen(str)){↵
printf("%d\n",(i-j));↵
j=lps[j-1];↵
}↵
}↵
printf("\n");↵
}↵
return 0;↵
}↵
What are some optimizations that I can apply on my code?
