Kodes/Z_Function.cpp at master · blank-27/Kodes · 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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<long long> vll;

vll makeZ(string s){
        ll n=s.size(),l=0,r=0,ind;
        vll z(n);
        z[0]=0;
        for(int i=1;i<n;i++){
            if(i>r){
                l=r=i;
                while(r<n and s[r]==s[r-l]) r++;
                r--;
                z[i]=r-l+1;
            }
            else{
                ind=i-l;
                if(i+z[ind]-1<r)    z[i]=z[ind];
                else{
                    l=i;
                    while(r<n and s[r]==s[r-l]) r++;
                    r--;
                    z[i]=r-l+1;
                }
            }
        }
        return z;
    }

    int main(){
        string s="abc$xabcabzabc";
        vll temp=makeZ(s);
        for(auto i:temp)    cout<<i<<" ";
    }