About kmp optimization

Revision en1, by Monster_Nerd, 2021-02-19 16:40:17

Recently i encountered TLE on this problem E. Tree-String Problem
using decent dfs + kmp. Later i came to know that there is an optimized version of kmp. I listed the code below which i had taken from Arpa 's code.

int k = 0; for(int i = 1; i < p.size(); i++){ while(k && p[i] != p[k]) k = f[k]; if(p[i] == p[k]) k++; f[i + 1] = k; } for(int i = 0; i < p.size(); i++) for(int j = 0; j < z; j++) nxt[i][j] = p[i] — 'a' == j ? i + 1 : bool(i) * nxt[ f[i] ][j];

now my question is, can i use it always [if memory limit is ok] ? Does it consistent and can anyone just briefly explain what does it do?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English Monster_Nerd 2021-02-19 23:14:03 8 Tiny change: 'j] = p[i] &mdash; 'a' == j ' -> 'j] = p[i] - 'a' == j '
en4 English Monster_Nerd 2021-02-19 16:43:10 18
en3 English Monster_Nerd 2021-02-19 16:42:08 20
en2 English Monster_Nerd 2021-02-19 16:41:13 6
en1 English Monster_Nerd 2021-02-19 16:40:17 730 Initial revision (published)