new distingct substring (spoj)

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

Автор jugal_sahu, 11 лет назад, По-английски

problem link : link

I have already solved distinct substring (spoj : link) but new distinct substring have strict timelimit.Please give me hint.....thanks

suffix array

jugal_sahu
11 лет назад
11

Комментарии (10)

Показать архивные | Написать комментарий?

VladaMG98

11 лет назад, скрыть # |

Suffix automaton solves this(maybe that is overkill, not sure).

→ Ответить

Harun

11 лет назад, скрыть # |

You can solve it in O(NlogN) with Suffix Array + Longest Common Prefix Array. Since same substrings will be in adcajent indexes in suffix array, you can easily eliminate them. I mean first calculate the number of same substrings then substract it from (N*(N+1))/2

→ Ответить

jugal_sahu

11 лет назад, скрыть # ^ |

Actually there is a problem distinct substring (easy one link:distinct substring). I have solved it using suffix array but new substring has strict timelimit.....please suggest

→ Ответить

Harun

11 лет назад, скрыть # ^ |

O(NlogN) will work with N <= 50,000. But if you want more optimal you can get suffix array and LCP array in O(N).

→ Ответить

jugal_sahu

11 лет назад, скрыть # ^ |

thanks I will try to do it with O(n)...

→ Ответить

Safrout

11 лет назад, скрыть # |

← Rev. 2 →

I have solved both actually using java 2 years ago using suffix array and LCP. I used a faster Suffix Array construction to pass the hard one. Do you want it?

→ Ответить

jugal_sahu

11 лет назад, скрыть # ^ |

Yes i want please give me your java code and explain how u optimized it....thanks

→ Ответить

Safrout

11 лет назад, скрыть # ^ |

This was my code for the easy problem

http://ideone.com/0BbVs3

The suffix array code is taken from competitive programming 3 and it gave me TLE for the hard version of the problem. So, I searched the internet for another suffix array implementation and actually I used it with the same approach.

Here is the code

http://ideone.com/kW5UFT

→ Ответить