I will be happy for a clue.
I need to find a randomized algorithm with probability of $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 $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 ot t=1), it will give a correct number with probability of $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 $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.