Z_Algorithm.cpp

// Z_Algorithm.cpp
#include <bits/stdc++.h>

using namespace std;

void Z_Algorithm(const char *s, int *z) {
	int n = strlen(s), l = 0, r = 0;
	for (int i = 1; i < n; i++) {
		if (i > r) {
			l = r = i;
			while (r < n && s[r - l] == s[r]) r++;
			z[i] = r - l; r --;
		} else if (z[i - l] < r - i + 1)
			z[i] = z[i-l];
		else { l = i;
			while (r < n && s[r - l] == s[r]) r ++;
			z[i] = r - l; r --;
		}
	}
}

int main() {
	char t[] = "penny fortune exercise child brick marine month child pour unity deer solid defend child straighten child host";
	char p[] = "child";
	int n = strlen(t) + strlen(p);
	char *s = (char*)malloc(n * sizeof(char));
	int *z = (int*)calloc(n, sizeof(int));
	int i = 0;
	int j = 0;
	while (p[i] != '\0') {
		s[i] = p[i];
		i++;
	}
	while (t[j] != '\0') {
		s[i + j] = t[j];
		j++;
	}
	Z_Algorithm(s, z);
	int count = 0;
	for (int i = 0; i < strlen(s); i++) {
		if (z[i] == strlen(p)) count++;
	}
	cout << "Tu " << p << " xuat hien " << count << " lan" << endl;
	return 0;
}