Блог пользователя krishna12345

Help Required(DP Problem — palindromic substring)

Автор krishna12345, история, 3 года назад, По-английски

Problem — https://www.hackerrank.com/contests/all-india-contest-by-mission-helix-a-31-october/challenges/palindromic-query/problem

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 года назад, # |
  Проголосовать: нравится 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.

→ Ответить