shahidul_brur's blog

What are the various applications of Z algorithm?
By shahidul_brur, 8 years ago, In English

I know that Z algorithm can be used for string matching. Which is: If we want to find P is S, then we calculate value of Z[] array using the string P + $(or any unused sign) + S. Then for any i, if Z[i] == |P|, then we state that P is found in S.

Now, I want to know other applications of Z algorithm. Please tell me what other kinds of problems we can solve using Z algorithm and how ?

Thanks in advance.

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

»
8 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

IMO, the problems that can be solved via Z Algorithm can, in almost all cases be solved via KMP with similar ease. I have sometimes found the converse to not be true. So you could use it to solve problems which are meant to be solved using KMP, however it might not always be as easy as it could be if KMP is used-although there indeed are problems where using Z algorithm might be simpler. 346B, you need KMP to solve it, I'm not sure if one can use Z Algorithm for this. Also, 291E

→ Reply