The problem was set in acm icpc preliminary contest 2017 in Dhaka site. Problem Link : E.Anti Hash

Problem is : you will given a string **S** of length **N** consisting of lowercase letters (a-z) only.Also given a base **B** and mod-value **M** for doing polynomial hashing. Note : **B** and **M** are both prime.

Your task is to find another string **T**, satisfying all of the following constraints: Length of **T** is exactly **N**. **T** consists of only lowercase letters (a-z). **T** and **S** have the same hash value that means, collision happens. For hashing in both case you have to use **B** and **M**.

Any idea? Thanks in advance.

For the subtask with

M≤ 10^{6}, you can have atmost 10^{6}different hashes. So, if you generate more than 10^{6}random strings, there is high probability that you'll hit one with same hash as the given string. However, you can't generate string naively. You can start with a string and try changing letters randomly.For

M< 2^{31}I don't know what to do.Probability is high because it's same to Birthday Paradox. If I generate M random string and mod with M then mod value will be 0 to M-1.So,the possible number of permutation of unique hash value of M random string is M! but total orientation of hash value is M^M.The probability of hash value being unique is M!/M^M. So,the probability of at least two hash value coincide is 1-(M!/M^M).

Generate

2sets of random strings of sizeceil(N/2)andfloor(N/2). Lets denote them as setAand setB. Let the size of each set isX. You can generate random strings by changing just a single random character of previous string as this will change the hash value randomly. Now generate their hashes. Now on, we only will deal with the hash values, forget the strings.For each hash value of set

B, we can say we need a desired hash from setAsuch that we can make the final hash value. Say hash value of an element of setBisH2. So we need another hash value from setA,H1such that this equation satisfies( H1 + (H2 << ceil(N/2)) ) % M = final_hash. Here shift operator denotes the polynomial shifting, hope it is understandable.Now, for the first

H2of setB, we will not be able to find the desiredH1with a probability(1-X/M). Now, as our desired hash value is not found in setAfor the first element, for the second element we can assume it's desired hash value will not collide with the first one's. So, now the sample space is reduced by one. So, this will also not match with a probability(1-X/(M-1)). For the third element the probability is(1-X/(M-2))and so on. This is the birthday paradox. With a good enough size of setAand setBthe probability of not finding desired pair becomes0. Like whenX = 1e4, chance of not finding is more than95%, whenX = 1e5, chance of not finding is less than1%. But when you takeX = 1e6, chance of not finding is way way close to0.I might miss some calculation here, but this is the idea.