### krishna12345's blog

By krishna12345, history, 3 weeks ago,

My solution — http://p.ip.fi/3RFY

Here i used dp approach (dp[i][j] where i = length of the substring , j = index of the substring ending with), passes all the sample test cases but getting segmentation fault in all the other test cases , Please look my code and tell my mistake.

Sorry for my bad english. Thank you .

• 0

 » 3 weeks ago, # |   0 $N$ can be as large as $2*10^6$.You cannot reserve enough space for a 2 dimensional DP array.You can solve this problem with String Hashing, answering each query in $O(1)$.This is a good resource for String hashing, the problem you are trying to solve is almost same as Problem 2 in the link.
•  » » 3 weeks ago, # ^ |   0 Thank you for the response.http://p.ip.fi/EixBHere i tried using string hashing(Getting TLE). I know we have to pre compute all the prefix hash and suffix hash and we should compare but i am getting some overflow errors while precomputing.Help me.
•  » » » 3 weeks ago, # ^ |   0 can you help me in the 2nd question "alternate substrings"
 » 3 weeks ago, # |   0 You can use Manacher's algorithm. It's $O(N)$, then $O(1)$ on each query.
•  » » 3 weeks ago, # ^ |   0 Thank you .