cpp/strings/z_algorithm.cpp at master · yashj0511/cpp · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/**
 *  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 = "This is a sample Testcase";
    string pat = "case";

    if (zAlgorithm(pat, tar))
    {
        cout << "'" << pat << "' found in string '" << tar << "'" << endl;
    }

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

    pat = "Kavya";

    if (zAlgorithm(pat, tar))
    {
        cout << "'" << pat << "' found in string '" << tar << "'" << endl;
    }

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

    return 0;
}