#include <bits/stdc++.h>

using namespace std;

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

void xoaKyTu(char *str, int k) {
	for (int i = k; i < strlen(str); i++)
		str[i] = str[i+1];
}

void chenKyTu(char *str, char x, int k) {
	int n = strlen(str);
	for (int i = n; i > k ; i--)
		str[i] = str[i-1];
	str[k] = x;
	str[n+1] = '\0';
}

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

int main() {
	char t[1000] = "toi co 1000, Nam co 21000, Dong co 1000 va 500";
	char p[] = "1000";
	char q[] = "mot nghin";
	int count = 0;
	count = Boyer_Moore_Horspool(t, p, q);
	cout << "Tu " << p << " xuat hien " << count << " lan" << endl;
	cout << "Chuoi sau khi thay the: " << endl;
	cout << t;
	return 0;
}