Recently i encountered TLE on this problem [E. Tree-String Problem](https://codeforces.net/contest/291/problem/E) ↵
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 [user:arpa,2021-02-19] '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?
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 [user:arpa,2021-02-19] '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++)
~~~~~↵
↵
↵
↵
↵
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?
