loan's blog

By loan, history, 4 years ago, In English

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!

  • Vote: I like it
  • +82
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +58 Vote: I do not like it

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