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;`↵
}`}````↵
`~~~~~`↵
`Your code here...`↵
`~~~~~`↵
``↵
```↵
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;`↵
`~~~~~`↵
`Your code here...`↵
`~~~~~`↵
``↵
```↵
What are some optimizations that I can apply on my code?
