Convolution and String Matching (small alphabet)

Правка en1, от snacache, 2018-05-10 19:07:47

Hi Codeforces community! I wanted to write this blog entry to help coders who would like to see a nice example of convolutions used in a problem which, at first sight, has little to no relation with polynomial multiplication (of course it has, it's a convolution after all)

The problem is as follows: You are given two strings S and P, with lengths n and m respectively, where m ≤ n

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский snacache 2018-05-11 05:08:43 4
en5 Английский snacache 2018-05-11 00:23:31 17 Tiny change: 'f_{a_i}(j) + f^{c}_{a_i}(j)}' -> 'f_{a_i}(j)}'
en4 Английский snacache 2018-05-10 23:54:16 62
en3 Английский snacache 2018-05-10 23:49:52 2787 Tiny change: '$ memory.<\b>\n\nThis' -> '$ memory.</b>\n\nThis' (published)
en2 Английский snacache 2018-05-10 21:17:51 2109 Tiny change: 'y, where $m\leqn$' -> 'y, where $n\beqm$'
en1 Английский snacache 2018-05-10 19:07:47 444 Initial revision (saved to drafts)