Simple Hash gives WA , double hash give TLE [ Longest Common Substring , ADAPHOTO , SPOJ]

Question : “https://www.spoj.com/problems/ADAPHOTO/

My solution -

  1. https://ideone.com/HJNFI7” [WA , single hash wa due to collision]
  2. https://ideone.com/pQPfDq”[TLE , double hash]

Help @everule1 @galencolin @ssjgz @ay2306

anyone ?

Try solving this with Suffix Array

If you dont know suffix array learn it from here:
https://codeforces.com/edu/course/2/lesson/2

I know , but is this not solved by Hashing ?

help @souradeep1999

Please help , @udayan14

Collision in unordered_set?

bro when I use double hash it gives me tle .

Can you use a boolean vector instead of unordered_set where you mark all values as true? Cause unordered set has O(n) worst case

Bro in double hash I use pair of unordered set , and each value of pair can lie 1 to 109+6 , not possible to declare this .

I think you can declare a bitset of that size

Bro we have to make pair in double hash , understand this thing.

Even double hash is giving WA. My submission using double hash https://ideone.com/4nLFAv

I found this online hope this helps

I also find out a solution (and submit too for check ), he uses his own hash table , and much complex things so I just leave the question as my approach is correct but no option left .

Thanks , instead of using unordered set of pair and find in it , we can use vector of pair and sort then take unique element and again for finding we can use binary search superb solution . Thanks once again.

No idea. I am very bad at string algorithms. I can try something with suffix array of the concatenated string and then building the lcp array. This might solve this question

2 Likes