PHP-Fusion Powered Website - Articles: Z-Algorithm in C++

Users Online

· Guests Online: 44

· Members Online: 0

· Total Members: 188
· Newest Member: meenachowdary055

Forum Threads

Newest Threads

No Threads created

Hottest Threads

No Threads created

Latest Articles

· Do while loop
· The for loop in C
· C while loop
· Pointers in C
· Functions in C

Oh no! Where's the JavaScript?
Your Web browser does not have JavaScript enabled or does not support JavaScript. Please enable JavaScript on your Web browser to properly view this Web site,
or upgrade to a Web browser that does support JavaScript; Firefox, Safari, Opera, Chrome or a version of Internet Explorer newer then version 6.

Articles Hierarchy

Articles Home » C++ » Z-Algorithm in C++

Z-Algorithm in C++

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

Users Online

Forum Threads

Latest Articles

Articles Hierarchy

Z-Algorithm in C++

Z-Algorithm in C++

Comments

Post Comment

Ratings