I will be happy for a clue.
I need to find a randomized algorithm with probability of $\frac{3}{4}$ and no more of $O(\log(n))$ bit's that send from $A$ to $B$.
$A$ and $B$ holding strings $as=(a_0,....a_{n-1})$ $bs=(b_0,....,b_{n-1})$. $A$ is composed from 0,1 only, and $B$ is composed from 0, 1, $t$, where $t$ can be 0 or 1. meaning: as=(001001) bs=(0t10tt) are identical. $A$ sends only one massage, and $B$ need to decided if $as=bs$.
If we know that $|t|=1$, I need to find a randomized algorithm with probability of $\frac{3}{4}$ to solve this problem. What I think to do is algorithm, based on Rabin-Karp algorithm, and run it twice - change $t$ to 1, and change $t$ to 0.
The algorithm will do the next steps: $A$ will choose coincidental number $(q)$ from 1 to $n^2$, and will calculate $r="as"\mod q$. it will send to $B$ ($q$ and $r$), and $B$ will do the same (will calculate $"bs" \mod q$, and will mark the answer as $j$). If $j=r-$ then $B$ will say identical, otherwise he will say "not identical". I succeeded to prove that if $B$ will check his string in one of the cases ($t=0$ or $t=1$), it will give a correct number with probability of $\frac{3}{4}$. But when I running it twice, I have a problem. Because I have more words to make a mistake with, and I successes only with probability of $\frac{1}{2}$.
After it I asked to give an algorithm if $t=|5\log(n)|$, and I thought to run it like with $t=1$, but I didn't succeed to improve the probability of that.
Thank you a lot for your help.