# Blog Archives

## z-algorithm for pattern matching

String algorithms are a traditional area of study in computer science and there is a wide variety of standard algorithms available. The more algorithms you know, the more easier it gets to work with them đź™‚ As the title of the post says, we will try to explore the z-algorithm today. Lets first formulate the problem statement and a couple of definitions. To start with lets look at the below mentioned question (from interviewstreet):

**QUESTION**

For two strings A and B, we define the similarity of the strings to be the length of the longest prefix common to both strings. For example, the similarity of strings â€śabcâ€ť and â€śabdâ€ť is 2, while the similarity of strings â€śaaaâ€ť and â€śaaabâ€ť is 3.

Calculate the sum of similarities of a string S with each of itâ€™s suffixes.

**Sample Input:**

2

ababaa

aa

**Sample Output:**

11

3

**Explanation:**

For the firstâ€¦

View original post 366 more words