Bai3.cpp

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

using namespace std;

struct SanPham {
	char *maSP;
	char *tenSP;
	int khoiLuong;
	int giaTri;
};

SanPham d[] = {
	{"SP0023", "Tivi Samsung 4K QLED", 10, 6},
	{"SP0024", "Tivi Sony 4K UltraHD", 10, 8},
	{"SP0025", "Tu lanh Samsung TC", 12, 8},
	{"SP0026", "Tu lanh Panasonic", 10, 9},
	{"SP0027", "Dien thoai Apple", 4, 12},
	{"SP0028", "Dien thoai Samsung", 5, 9},
	{"SP0029", "Dien thoai Oppo Find", 5, 7},
	{"SP0030", "May lanh Panasonic", 9, 7},
};

int n = 7;

void Swap(SanPham &a, SanPham &b) {
	SanPham tmp = a;
	a = b;
	b = tmp;
}

int Quick_Sort(SanPham a[], int left, int right) {
	char pivot[100];
	strcpy(pivot, a[(left + right) / 2].tenSP);
	int i = left;
	int j = right;
	while (i < j) {
		while (strcmp(a[i].tenSP, pivot) < 0) {
			i++;
		}
		while (strcmp(a[j].tenSP, pivot) > 0) {
			j--;
		}
		if (i <= j) {
			Swap(a[i], a[j]);
			i++;
			j--;
		}
	}
	if (i < right) {
		Quick_Sort(a, i, right);
	}
	if (left < j) {
		Quick_Sort(a, left, j);
	}
}

int TimViTri(SanPham a[], int l, int r, SanPham b) {
	if (l == r) {
		if (strcmp(a[l].tenSP, b.tenSP) > 0) return l;
		else return n + 1;
	} else {
		int m = (l + r) / 2;
		int pos1 = TimViTri(a, l, m, b);
		int pos2 = TimViTri(a, m + 1, r, b);
		if (pos1 < pos2) return pos1;
		else return pos2;
	}
}

int XauConChung(char a[], char b[]) {
	int n = strlen(a);
	int m = strlen(b);
	int L[n + 1][m + 1];
	for (int i = 0; i <= n; i++) L[i][0] = 0;
	for (int j = 0; j <= m; j++) L[0][j] = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (a[i - 1] == b[j - 1])
				L[i][j] = L[i - 1][j - 1] + 1;
			else
				L[i][j] = max(L[i - 1][j], L[i][j - 1]);
	return L[n][m];
}

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

int main() {
	Quick_Sort(d, 0, n);
	for (int i = 0; i <= n; i++) {
		cout << d[i].maSP << "\t" << d[i].tenSP << "\t" << d[i].khoiLuong << "\t" << d[i].giaTri << endl;
	}
	cout << endl;
	SanPham sp = {"SP0088", "May giat Samsung 10KG", 12, 9};
	cout << "Vi tri co the chen SP0088 la: " << TimViTri(d, 0, n, sp) << endl;
	cout << endl;
	cout << "Cac san pham giong SP0088 la: " << endl;
	for (int i = 0; i <= n; i++) {
		if (XauConChung(d[i].tenSP, sp.tenSP) > 10)
			cout << d[i].maSP << "\t" << d[i].tenSP << "\t" << d[i].khoiLuong << "\t" << d[i].giaTri << endl;
	}
	int count = 0;
	for (int i = 0; i <= n; i++) {
		if (Boyer_Moore_Horspool(d[i].tenSP, "Tivi") > 0) {
			count++;
			break;
		}
	}
	if (count > 0)
		cout << endl << "Trong danh sach d co tivi" << endl;
	else
		cout << endl << "Trong danh sach d khong co tivi" << endl;
	return 0;
}