Template_for_CP/zfunction.cpp at master · aneesh2312/Template_for_CP · 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
template<class holderType>
class ZFunction {

public:
	holderType arr;
	vector< int > z;
	ZFunction(holderType var) {
		arr = var;
		z.resize((int) arr.size() + 1);
	}

	void build() {
		z[0] = 0;
		int l = 0, r = 0;
		for (int i = 1; i < arr.size(); i++) {
			if (i <= r) {
				z[i] = min(r-i+1, z[i-l]);
				for (int j = i+z[i]; j < arr.size(); j++) {
					if (arr[j] == arr[j-i]) {
						z[i]++;
					} else {
						break;
					}
				}
				if (i + z[i] - 1 > r) {
					l = i;
					r = i + z[i] - 1;
				}
			} else {
				z[i] = 0;
				for (int j = i; j < arr.size(); j++) {
					if (arr[j] == arr[j-i]) {
						z[i]++;
					} else {
						break;
					}
				}

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

	void change(holderType newVar) {
		arr = newVar;
		z.resize((int) newVar.size() + 1);
		build();
	}
};