BoyreMoore:
#include <stdio.h>
#include <string.h>
#define MAX 256 // ASCII range
void buildBadMatchTable(char pattern[], int badChar[], int m) {
int i;
for (i = 0; i < MAX; i++) badChar[i] = m;
printf("Step-by-step Bad Match Table Construction:\n");
printf("Initially, all characters set to %d\n\n", m);
for (i = 0; i < m - 1; i++) {
int shift = m - i - 1;
badChar[(unsigned char)pattern[i]] = shift;
printf("Pattern[%d] = '%c' → bad match value = max(1, %d - %d - 1) = %d\n",
i, pattern[i], m, i, shift);
badChar[(unsigned char)pattern[m - 1]] = m;
printf("Pattern[%d] = '%c' (last character) → bad match value = %d (special rule)\n\n",
m - 1, pattern[m - 1], m);
printf("Final Bad Match Table (unique pattern chars shown):\n");
int printed[256] = {0};
for (i = 0; i < m; i++) {
unsigned char c = pattern[i];
if (!printed[c]) {
printf(" '%c' : %d\n", c, badChar[c]);
printed[c] = 1;
printf(" '*' (all other chars) : %d\n\n", m);
void boyerMooreSearch(char text[], char pattern[]) {
int n = strlen(text);
int m = strlen(pattern);
int badChar[MAX];
buildBadMatchTable(pattern, badChar, m);
printf("=== Pattern Matching Process (showing each comparison) ===\n\n");
int startIndex = 0;
while (startIndex <= n - m) {
int j = m - 1;
printf("Starting index for the comparison is %d:\n", startIndex);
printf("Text : %s\n", text);
printf("Pattern: ");
for (int s = 0; s < startIndex; s++) putchar(' ');
printf("%s\n\n", pattern);
// Compare right to left
while (j >= 0) {
char pc = pattern[j];
char tc = text[startIndex + j];
if (pc == tc) {
printf("Compare pattern[%d] = '%c' with text[%d] = '%c' → Match\n",
j, pc, startIndex + j, tc);
j--;
} else {
printf("Compare pattern[%d] = '%c' with text[%d] = '%c' → Mismatch\n",
j, pc, startIndex + j, tc);
int badValue = badChar[(unsigned char)tc];
if (badValue < 1) badValue = 1;
printf("Bad match value for text character '%c' = %d\n", tc, badValue);
int newStart = startIndex + badValue;
if (newStart > n - m)
newStart = n - m + 1; // prevent overflow
printf("→ New starting index for the comparison is %d\n\n", newStart);
startIndex = newStart;
break;
if (j < 0) {
printf("\n✅ Full pattern match found at starting index %d (0-based)\n", startIndex);
return;
printf("\n✅ Pattern not found in text.\n");
int main() {
char text[] = "welcometeammast";
char pattern[] = "teammast";
printf("Text : %s\n", text);
printf("Pattern : %s\n\n", pattern);
boyerMooreSearch(text, pattern);
return 0;
}
Quick Sort:
#include <stdio.h>
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
printf("\n");
int partition(int arr[], int low, int high) {
int pivot = arr[low];
int l = low + 1;
int r = high;
int temp;
while (l <= r) {
while (l <= r && arr[l] <= pivot) {
l++;
while (l <= r && arr[r] > pivot) {
r--;
if (l < r) {
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
// Place pivot in its correct position
temp = arr[low];
arr[low] = arr[r];
arr[r] = temp;
return r; // pivot index
void quickSort(int arr[], int low, int high, int n) {
if (low < high) {
int pi = partition(arr, low, high);
printf("After partition around pivot %d (index %d): ", arr[pi], pi);
printArray(arr, n);
quickSort(arr, low, pi - 1, n);
quickSort(arr, pi + 1, high, n);
int main() {
int n = 9;
int arr[9];
printf("Enter 9 elements:\n");
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
quickSort(arr, 0, n - 1, n);
printf("\nSorted array:\n");
printArray(arr, n);
return 0;
}
Merge Sort:
#include <stdio.h>
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
printf("\n");
void merge(int arr[], int left, int mid, int right, int n) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
while (i < n1) {
arr[k++] = L[i++];
while (j < n2) {
arr[k++] = R[j++];
printf("After merging (%d to %d): ", left, right);
printArray(arr, n);
void mergeSort(int arr[], int left, int right, int n) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid, n);
mergeSort(arr, mid + 1, right, n);
merge(arr, left, mid, right, n);
}
int main() {
int n = 9;
int arr[9];
printf("Enter 9 elements:\n");
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
printf("\n=== Merge Sort Process ===\n");
mergeSort(arr, 0, n - 1, n);
printf("\nSorted array:\n");
printArray(arr, n);
return 0;
}
KMP
#include <stdio.h>
#include <string.h>
void computeLPSArray(char* pat, int M, int* lps) {
int len = 0; // length of the previous longest prefix suffix
int i = 1;
lps[0] = 0; // lps[0] is always 0
printf("Constructing LPS array for pattern: %s\n", pat);
printf("Index\tCharacter\tLPS\n");
printf("0\t%c\t\t%d\n", pat[0], lps[0]);
while (i < M) {
if (pat[i] == pat[len]) {
len++;
lps[i] = len;
printf("%d\t%c\t\t%d (match)\n", i, pat[i], lps[i]);
i++;
} else {
if (len != 0) {
len = lps[len - 1];
printf("%d\t%c\t\t-- (mismatch, update len to %d)\n", i, pat[i], len);
} else {
lps[i] = 0;
printf("%d\t%c\t\t%d (mismatch, len=0)\n", i, pat[i], lps[i]);
i++;
printf("\n");
void KMPSearch(char* pat, char* txt) {
int M = strlen(pat);
int N = strlen(txt);
int lps[M];
computeLPSArray(pat, M, lps);
int i = 0; // index for txt[]
int j = 0; // index for pat[]
printf("=== Starting KMP Search ===\n");
printf("Text : %s\n", txt);
printf("Pattern: %s\n\n", pat);
while (i < N) {
printf("Compare txt[%d] = '%c' and pat[%d] = '%c' → ", i, txt[i], j, pat[j]);
if (pat[j] == txt[i]) {
printf("Match\n");
i++;
j++;
} else {
printf("Mismatch\n");
if (j != 0) {
int old_j = j;
j = lps[j - 1];
printf("→ Update j from %d to lps[%d] = %d\n", old_j, old_j - 1, j);
} else {
i++;
if (j == M) {
printf("✅ Pattern found at index %d\n", i - j);
j = lps[j - 1];
int main() {
char txt[100], pat[100];
printf("Enter text: ");
fgets(txt, sizeof(txt), stdin);
txt[strcspn(txt, "\n")] = '\0'; // remove newline
printf("Enter pattern: ");
fgets(pat, sizeof(pat), stdin);
pat[strcspn(pat, "\n")] = '\0'; // remove newline
printf("\n");
KMPSearch(pat, txt);
return 0;