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

My solution -

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

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

My solution -

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

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 ?

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 10^{9}+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.

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