Bai2.cpp

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

using namespace std;

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) {
			count++;
			j == 0;
		}
	}
	return count;
}

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 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, 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[] = "penny fortune exercise child brick marine month child pour unity deer solid defend child straighten child host";
	char p[] = "child";
	char p2[] = "children";
	cout << t << endl;
	cout << "Tu " << p << " xuat hien " << indexOf(p, t) << " lan" << endl;
	Boyer_Moore_Horspool(t, p, p2);
	cout << "Chuoi sau khi thay the" << endl;
	cout << t << endl;
	return 0;
}