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

ssrivastava990 · August 29, 2020, 7:59am

Question : “SPOJ.com - Problem ADAPHOTO”

My solution -

“HJNFI7 - Online C++0x Compiler & Debugging Tool - Ideone.com” [WA , single hash wa due to collision]
“pQPfDq - Online C++0x Compiler & Debugging Tool - Ideone.com”[TLE , double hash]

Help @everule1 @galencolin @ssjgz @ay2306

ssrivastava990 · August 29, 2020, 8:48am

anyone ?

echo_abhinav · August 29, 2020, 10:55am

Try solving this with Suffix Array

If you dont know suffix array learn it from here:

ssrivastava990 · August 29, 2020, 10:57am

I know , but is this not solved by Hashing ?

ssrivastava990 · August 29, 2020, 11:53am

help @souradeep1999

ssrivastava990 · August 30, 2020, 6:58am

Please help , @udayan14

preyam · August 30, 2020, 10:00pm

Collision in unordered_set?

ssrivastava990 · August 31, 2020, 6:03am

bro when I use double hash it gives me tle .

preyam · August 31, 2020, 6:10am

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

ssrivastava990 · August 31, 2020, 6:11am

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

preyam · August 31, 2020, 6:20am

I think you can declare a bitset of that size

ssrivastava990 · August 31, 2020, 6:21am

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

strelkinite · August 31, 2020, 8:09am

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

echo_abhinav · August 31, 2020, 8:14am

I found this online hope this helps

github.com

IvanIsCoding/OlympiadSolutions/blob/master/SPOJ/ADAPHOTO.cpp

// Ivan Carvalho
// Solution to https://www.spoj.com/problems/ADAPHOTO/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
const ll MOD1 = 1e9 + 9;
const ll prime1 = 999983;
const ll MOD2 = 1e9 + 7;
const ll prime2 = 999979;
const ll invprime1 = 943912055;
const ll invprime2 = 672490127;
const int MAXN = 1e6 + 10;
char entrada[2][MAXN];
bitset<MOD1 + 2> conjunto1, conjunto2;
ll hash1[2][MAXN], pot1[MAXN], invpot1[MAXN], hash2[2][MAXN], pot2[MAXN],
    invpot2[MAXN];
int N, M;
ll get_hash1(int id, int a, int b) {
    ll val = ((hash1[id][b] - hash1[id][a - 1]) * invpot1[a - 1]) % MOD1;

This file has been truncated. show original

ssrivastava990 · August 31, 2020, 8:19am

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 .

ssrivastava990 · August 31, 2020, 8:22am

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.

udayan14 · August 31, 2020, 5:08pm

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