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?