Z-Algorithm in C++ - Sanfoundry

This C++ Program demonstrates the implementation of Z-Algorithm.

Here is source code of the C++ Program to implement Z-Algorithm. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 * C++ Program to Implement Z-Algorithm

```
 */
```
```
#include <iostream>
```
```
#include <cstring>
```
```
#include <vector>
```
```
using namespace std;
```

bool zAlgorithm(string pattern, string target)

```
{
```
```
    string s = pattern + '$' + target;
```
```
    int n = s.length();
```
```
    vector<int> z(n, 0);
```
```
    int goal = pattern.length();
```
```
    int r = 0, l = 0, i;
```
```
    for (int k = 1;  k < n; k++)
```
```
    {
```
```
        if (k > r)
```
```
        {
```

            for (i = k; i < n && s[i] == s[i - k]; i++);

```
            if (i > k)
```
```
            {
```
```
                z[k] = i - k;
```
```
                l = k;
```
```
                r = i - 1;
```
```
            }
```
```
        }
```
```
        else
```
```
        {
```

            int kt = k - l, b = r - k + 1;

```
            if (z[kt] > b)
```
```
            {
```

                for (i = r + 1; i < n && s[i] == s[i - k]; i++);

```
                z[k] = i - k;
```
```
                l = k;
```
```
                r = i - 1;
```
```
            }
```
```
        }
```
```
        if (z[k] == goal)
```
```
            return true;
```
```
    }
```
```
    return false;
```
```
}
```
```
 
```
```
int main()
```
```
{
```

    string tar = "san and linux training";

```
    string pat = "lin";
```
```
    if (zAlgorithm(pat, tar))
```

        cout<<"'"<<pat<<"' found in string '"<<tar<<"'"<<endl;

```
    else
```

        cout<<"'"<<pat<<"' not found in string '"<<tar<<"'"<<endl;

```
    pat = "sanfoundry";
```
```
    if (zAlgorithm(pat, tar))
```

        cout<<"'"<<pat<<"' found in string '"<<tar<<"'"<<endl;

```
    else
```

        cout<<"'"<<pat<<"' not found in string '"<<tar<<"'"<<endl;

```
    return 0;
```
```
}
```

$ g++ z-algorithm.cpp
$ a.out
 
'lin' found in string 'san and linux training'
'sanfoundry' not found in string 'san and linux training'
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

If you wish to look at all C++ Programming examples, go to C++ Programs.

« Prev - Extended Euclidean Algorithm in C++

» Next - C++ Program to Find All Pairs Shortest Path

Related Posts:

Recommended Articles: