I recently stumbled upon this beautiful problem, but I didn't manage to solve it and I don't have a clue about its solution.

It basicaly asks you to count the number of pairs $$$(s, t)$$$, where $$$s$$$ and $$$t$$$ are strings and $$$t$$$ is a substring of $$$s$$$. Size of $$$s$$$ is $$$N <= 200$$$ and size of $$$t$$$ is $$$M <= 50$$$, also the alphabet size is $$$A <= 1000$$$.

This is the link to the contest.

I will greatly appreciate any ideas on how to solve this problem and if you know some similar problems, please let me know.

Thanks in advance!

Here's a discussion of this problem from way back by Petr.

Thank you very much!