Monster_Nerd's blog

By Monster_Nerd, history, 4 years ago, In English

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?

Full text and comments »

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