I came across the problem, where I'd like to determine if the number is of the form $$x=\overline{d_md_{m-1}...d_2d_1d_Md_{M-1}...d_2d_1}$$ in some chosen base, where $d_i$ present a single digit. This representation effectively means that the first $m$ digits is the same as the last $m$ digits. We can assume that $M \geq m$ so the starting digits does not overlap with the ending digits. Beside that, I do not have any information about $m$ or $M$.
Now, the question is, can I efficiently determine if the number is of this form or not? The base is chosen upfront, so the question is not for a general base. And I do not actually have to find out what $m$ is, I'm just interested if the number is of the desired form. Furthermore, I will be happy already with the some probabilistic approach, where result is given with a high probability.
What I have thought of so far
What id written below is done for special case where the chosen number base is 10
Special case $m=M$
Then we can write
$$x=\overline{d_Md_{M-1}...d_2d_1d_Md_{M-1}...d_2d_1} = \overline{d_Md_{M-1}...d_2d_1}(10^M+1)$$ The number of digits in the representation is $2M$ (can be calculated easiliy) and then I check if $x=0\mod{(10^M+1)}$
General case
I can similarly write
$$x=\overline{d_md_{m-1}...d_2d_1d_Md_{M-1}...d_2d_1}=\overline{d_md_{m-1}...d_2d_1}(10^M+1)+\overline{d_Md_{M-1}...d_{m+2}d_{m+1}}10^m$$ Problem here is that I do not know anything about $m$ or $M$.
What I can do is that I calculate first $l$ digits. I had an idea if I can somehow prove that the same sequence can be observed in the number $x-\overline{d_md_{m-1}...d_{m-l+1}}10^{m-l+M}$, I would be on the right track. I $l$ is big enough I can be pretty confident the number is of the desired form. But I just could not find a way. Maybe some homomorphism can help here, I don't know.
These are just my thoughts, if you can direct me to some other approach, I'm happy to look into it.