Need help in solving Problem I Substring Pairs from 2014-2015 Petrozavodsk Winter Training Camp, Contest.58 (Makoto rng_58 Soejima contest)

Revision en2, by giotozila, 2020-09-26 13:43:05

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!

Tags #string, #counting, #help


  Rev. Lang. By When Δ Comment
en2 English giotozila 2020-09-26 13:43:05 32 Tiny change: ' of pairs (s, t), where s ' -> ' of pairs <tex>(s, t)</tex>, where s '
en1 English giotozila 2020-09-26 13:38:22 699 Initial revision (published)