A note on CF1721E (EDU134E) Prefix Function Queries

Правка en2, от GrandLisboa, 2023-03-24 18:58:00

Problem Link

Submission Link

Part 1: Calculate the Prefix function (next array) in $$$O(n)$$$

We can calculate the prefix function (next array) in linear time using the following code:

Теги string, kmp, prefix function

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en20 Английский GrandLisboa 2023-03-25 10:39:02 4 Tiny change: '~~~~\n\nWhile is it $O(' -> '~~~~\n\nWhy is it $O('
en19 Английский GrandLisboa 2023-03-25 07:26:22 4 Tiny change: 'we define a last arra' -> 'we define the last arra'
en18 Английский GrandLisboa 2023-03-24 19:57:32 0 (published)
en17 Английский GrandLisboa 2023-03-24 19:57:24 2 (saved to drafts)
en16 Английский GrandLisboa 2023-03-24 19:41:51 0 (published)
en15 Английский GrandLisboa 2023-03-24 19:41:40 2 Tiny change: ' `last[i][c]` from `l' -> ' `last[i][*]` from `l'
en14 Английский GrandLisboa 2023-03-24 19:41:21 881
en13 Английский GrandLisboa 2023-03-24 19:35:27 1158
en12 Английский GrandLisboa 2023-03-24 19:28:51 1 Tiny change: 'algorithm?$**\n\n(1)T' -> 'algorithm?**\n\n(1)T'
en11 Английский GrandLisboa 2023-03-24 19:27:43 383
en10 Английский GrandLisboa 2023-03-24 19:24:01 343
en9 Английский GrandLisboa 2023-03-24 19:21:42 200
en8 Английский GrandLisboa 2023-03-24 19:20:11 228
en7 Английский GrandLisboa 2023-03-24 19:13:12 407
en6 Английский GrandLisboa 2023-03-24 19:10:12 4
en5 Английский GrandLisboa 2023-03-24 19:09:51 178
en4 Английский GrandLisboa 2023-03-24 19:07:53 382
en3 Английский GrandLisboa 2023-03-24 19:01:23 234
en2 Английский GrandLisboa 2023-03-24 18:58:00 111
en1 Английский GrandLisboa 2023-03-24 18:55:37 239 Initial revision (saved to drafts)