DAA LAB DA-3

NAME: KAVINKUMAR.EK
REGN. NO: 23BCE0421

1) MAXIMUM SUM SUB ARRAY USING DIVIDE AND CONQUER ALGORITHM:

CODE:

#include <stdio.h>
#include <limits.h>
int max_crossing_sum(int arr[], int low, int mid, int high, int* cross_start, int* cross_end) {
int sum = 0;
int left_sum = INT_MIN;
int start_left = mid;
for (int i = mid; i >= low; i--) {
sum += arr[i];
if (sum > left_sum) {
left_sum = sum;
start_left = i;
}
}
sum = 0;
int right_sum = INT_MIN;
int end_right = mid + 1;
for (int i = mid + 1; i <= high; i++) {
sum += arr[i];
if (sum > right_sum) {
right_sum = sum;
end_right = i;
}
}
*cross_start = start_left;
*cross_end = end_right;
return left_sum + right_sum;
}
int max_subarray_sum(int arr[], int low, int high, int* start, int* end) {
if (low == high) {
*start = low;
*end = high;
return arr[low];
}
int mid = (low + high) / 2;
int left_start, left_end, right_start, right_end, cross_start, cross_end;
int left_sum = max_subarray_sum(arr, low, mid, &left_start, &left_end);
int right_sum = max_subarray_sum(arr, mid + 1, high, &right_start, &right_end);
int cross_sum = max_crossing_sum(arr, low, mid, high, &cross_start, &cross_end);
if (left_sum >= right_sum && left_sum >= cross_sum) {
*start = left_start;
*end = left_end;
return left_sum;
}
else if (right_sum >= left_sum && right_sum >= cross_sum) {
*start = right_start;
*end = right_end;
return right_sum;
}
else {
*start = cross_start;
*end = cross_end;
return cross_sum;
}
}
int main() {
int n;
printf("Enter the number of elements: ");
scanf("%d", &n);
if (n <= 0) {
printf("Invalid array size!\n");
return 1;
}
int arr[n];
printf("Enter %d elements:\n", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
int start = 0, end = 0;
int max_sum = max_subarray_sum(arr, 0, n - 1, &start, &end);
printf("Maximum Subarray Sum: %d\n", max_sum);
printf("Subarray: [");
for (int i = start; i <= end; i++) {
printf("%d%s", arr[i], i == end ? "" : ", ");
}
printf("]\n");
return 0;
}
2) STRING MATCHING ALGORITHMS:
a) NAÏVE’S APPROACH:

CODE:

#include <stdio.h>
#include <string.h>

void naiveStringMatch(char* text, char* pattern) {

int n = strlen(text);
int m = strlen(pattern);
int found = 0;

for (int i = 0; i <= n - m; i++) {

int j;

for (j = 0; j < m; j++) {

if (text[i + j] != pattern[j])
break;
}

if (j == m) {
printf("Pattern found at index %d\n", i);
found = 1;
}
}

if (!found) {
printf("Pattern not found in text\n");
}
}
int main() {
char text[1000], pattern[100];

printf("Enter the text: ");

scanf("%[^\n]s", text);

getchar();

printf("Enter the pattern to search: ");

scanf("%[^\n]s", pattern);

naiveStringMatch(text, pattern);

return 0;
}

OUTPUT:

b) RABIN KARP’S ALGORITHM:

CODE:

#include <stdio.h>
#include <string.h>

#define d 256
#define q 101

void rabinKarp(char* text, char* pattern) {

int n = strlen(text);
int m = strlen(pattern);
 int i, j;
int p = 0;
int t = 0;
int h = 1;
int found = 0;

for (i = 0; i < m - 1; i++)

h = (h * d) % q;

for (i = 0; i < m; i++) {

p = (d * p + pattern[i]) % q;
t = (d * t + text[i]) % q;
}

for (i = 0; i <= n - m; i++) {

if (p == t) {
for (j = 0; j < m; j++) {
if (text[i + j] != pattern[j])
break;
}
if (j == m) {
printf("Pattern found at index %d\n", i);
found = 1;
}
}

if (i < n - m) {
t = (d * (t - text[i] * h) + text[i + m]) % q;
if (t < 0)
t = t + q;
}
}

if (!found) {
printf("Pattern not found in text\n");
}
}

int main() {
char text[1000], pattern[100];

printf("Enter the text: ");

scanf("%[^\n]s", text);

getchar();

printf("Enter the pattern to search: ");

scanf("%[^\n]s", pattern);
 rabinKarp(text, pattern);

return 0;
}

OUTPUT:

c) KMP ALGORITHM:

CODE:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void computeLPSArray(char* pattern, int M, int* lps) {

int len = 0;
int i = 1;
lps[0] = 0;

while (i < M) {
if (pattern[i] == pattern[len]) {
len++;
lps[i] = len;
i++;
}
else {
if (len != 0) {
len = lps[len - 1];
}
else {
lps[i] = 0;
i++;
}
}
}
}
void KMPSearch(char* pattern, char* text) {
int M = strlen(pattern);
int N = strlen(text);
int found = 0;

int* lps = (int*)malloc(M * sizeof(int));

computeLPSArray(pattern, M, lps);

int i = 0;
int j = 0;

while (i < N) {
if (pattern[j] == text[i]) {
j++;
i++;
}

if (j == M) {
printf("Pattern found at index %d\n", i - j);
found = 1;
j = lps[j - 1];
}
else if (i < N && pattern[j] != text[i]) {
if (j != 0)
j = lps[j - 1];
else
i++;
}
}

if (!found) {
printf("Pattern not found in text\n");
}

free(lps);
}

int main() {
char text[1000], pattern[100];

printf("Enter the text: ");

scanf("%[^\n]s", text);

getchar();
 printf("Enter the pattern to search: ");
scanf("%[^\n]s", pattern);

KMPSearch(pattern, text);

return 0;
}

OUTPUT: