#include <bits/stdc++.h>

using namespace std;

struct DanhSach {
	char xau[100];
};

DanhSach d[] = {
	"Hello from the other side",
	"Hello friend, My name is c++",
	"My name is c++",
	"Ung dung thuat toan",
	"Mon hoc thuat toan ung dung"
};

int Min(DanhSach a[], int l, int r) {
	if (r == l) return l;
	else {
		int m = (l + r) / 2;
		int pos1 = Min(a, l, m);
		int pos2 = Min(a, m + 1, r);
		if (strlen(a[pos1].xau) < strlen(a[pos2].xau)) return pos1;
		return pos2;
	}
}

int Sum(DanhSach a[], int l, int r) {
	if (r == l) {
		return strlen(a[l].xau);
	} else {
		int m = (l + r) / 2;
		return Sum(a, l, m) + Sum(a, m + 1, r);
	}
}

DanhSach b[100];
void MergeSort(DanhSach a[], int l, int r) {
	if (r > l) {
		int i, j;
		int m = (l + r) / 2;
		MergeSort(a, l, m);
		MergeSort(a, m + 1, r);
		for (i = m; i >= l; i--) b[i] = a[i];
		for (j = m + 1; j <= r; j++) b[r + m + 1 - j] = a[j];
		i = l; j = r;
		for (int k = l; k <= r; k++) {
			if (strlen(b[i].xau) < strlen(b[j].xau)) {
				a[k] = b[i];
				i++;
			} else {
				a[k] = b[j];
				j--;
			}
		}
	}
}

int indexOf(const char *p, const char *t) {
	int m = strlen(p);
	int n = strlen(t) - m;
	int count = 0;
	for (int i = 0; i <= n; i++) {
		int j = 0;
		while (j < m && t[i + j] == p[j]) {
			j++;
		}
		if (j == m) {
			return i;
		}
	}
	return -1;
}

int Search(DanhSach a[], char *st, int l, int r) {
	if (r == l) {
		if (indexOf(st, a[l].xau) > 0) return l;
		else return -1;
	} else {
		int m = (l + r) / 2;
		int pos1 = Search(a, st, l, m);
		int pos2 = Search(a, st, m + 1, r);
		if (pos1 >= 0) return pos1;
		if (pos2 >= 0) return pos2;
	}
}

int char_in_string(char T, char *P) {
	int i = 0;
	while (P[i] != '\0') {
		if (P[i] == T) return i;
		i++;
	}
	return -1;
}

int Boyer_Moore_Horspool(char *T, char *P) {
	int dem = 0, i = strlen(P) - 1, v = strlen(P);
	while (i < strlen(T)) {
		int x = v - 1, j = i;
		while (T[j] == P[x] && x > -1) {
			j--; x--;
		}
		if (x < 0) {
			dem++; i = i + v;
		} else {
			x = char_in_string(T[j], P);
			if (x < 0) i = i + v;
			else i = j + v - x - 1;
		}
	}
	return dem;
}

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 --;
		}
	}
}

void TinhChieuDai() {
	int pos = Min(d, 0, 4);
	cout << "Xau co chieu dai nho nhat la: " << pos << endl;
	cout << d[pos].xau << endl;
	cout << "\nTong chieu dai cac xau ky tu la: " << Sum(d, 0, 4) << endl;
}

void SapXep() {
	MergeSort(d, 0, 4);
	cout << "\nDanh sach xau ky tu sau khi sap xep: " << endl;
	for (int i = 0; i < 5; i++) {
		cout << d[i].xau << endl;
	}
}

void TimKiem1() {
	char st[100];
	cout << "Nhap xau ky tu st bat ky: ";
	fflush(stdin); gets(st);
	int pos = Search(d, st, 0, 4);
	if (pos != -1) {
		cout << "Vi tri xuat hien: " << pos << endl;
		cout << d[pos].xau << endl;
	} else {
		cout << "Khong tim thay" << endl;
	}
}

void TimKiem2() {
	char st[] = "name";
	int dem = 0;
	cout << "\nCac xau xuat hien tu " << st << " la: " << endl;
	for (int i = 0; i < 5; i++) {
		int z = Boyer_Moore_Horspool(d[i].xau, st);
		if (z > 0) {
			dem += z;
			cout << d[i].xau << endl;
		}
	}
	cout << "Tu " << st << " xuat hien " << dem << " lan" << endl;
}

void TimKiem3() {
	cout << endl;
	for (int k = 1; k < 5; k++) {
		int n = strlen(d[k].xau) + strlen(d[0].xau);
		char *s = (char*)malloc(n * sizeof(char));
		int *z = (int*)calloc(n, sizeof(int));
		int i = 0, j = 0;
		while (d[0].xau[i] != '\0') {
			s[i] = d[0].xau[i];
			i++;
		}
		while (d[k].xau[j] != '\0') {
			s[i + j] = d[k].xau[j];
			j++;
		}
		Z_Algorithm(s, z);
		int count = 0;
		for (int i = 0; i < strlen(s); i++) {
			if (z[i] == strlen(d[0].xau)) count++;
		}
		//if (count > 0)
			//cout << "Xau " << d[0].xau << " la xau con cua xau " << d[k].xau << endl;
		cout << "Xau d[0] xuat hien " << count << " lan trong xau d[" << k << "]" << endl;
	}
	
}

int main() {
	TinhChieuDai();
	SapXep();
	TimKiem1(); //Chia de tri
	TimKiem2(); //Boyer Moore Horspool
	TimKiem3(); //Z_Algorithm
	return 0;
}