[go: up one dir, main page]
Scribd
Upload
11 views3 pages

DP C Programs User Input

The document contains three C programs that implement dynamic programming algorithms for string analysis. The first program calculates the Longest Common Subsequence, the second finds the Longest Repeating Subsequence, and the third determines the Longest Common Substring. Each program prompts the user for input and outputs the length of the respective subsequence or substring.

Uploaded by

jonnamalarakesh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
11 views3 pages

DP C Programs User Input

The document contains three C programs that implement dynamic programming algorithms for string analysis. The first program calculates the Longest Common Subsequence, the second finds the Longest Repeating Subsequence, and the third determines the Longest Common Substring. Each program prompts the user for input and outputs the length of the respective subsequence or substring.

Uploaded by

jonnamalarakesh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Dynamic Programming C Programs (User Input Version)

1. Longest Common Subsequence


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

int max(int a, int b) {


return (a > b) ? a : b;
}

int main() {
char text1[100], text2[100];
printf("Enter first string: ");
scanf("%s", text1);
printf("Enter second string: ");
scanf("%s", text2);

int m = strlen(text1);
int n = strlen(text2);
int dp[m + 1][n + 1];

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


for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0)
dp[i][j] = 0;
else if (text1[i - 1] == text2[j - 1])
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}

printf("Length of Longest Common Subsequence: %d\n", dp[m][n]);


return 0;
}
2. Longest Repeating Subsequence
----------------------------------
#include <stdio.h>
#include <string.h>

int max(int a, int b) {


return (a > b) ? a : b;
}

int main() {
char str[100];
printf("Enter the string: ");
scanf("%s", str);

int n = strlen(str);
int dp[n + 1][n + 1];

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


for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0)
dp[i][j] = 0;
else if (str[i - 1] == str[j - 1] && i != j)
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}

printf("Length of Longest Repeating Subsequence: %d\n", dp[n][n]);


return 0;
}
3. Longest Common Substring
-----------------------------
#include <stdio.h>
#include <string.h>

int max(int a, int b) {


return (a > b) ? a : b;
}

int main() {
char s1[100], s2[100];
printf("Enter first string: ");
scanf("%s", s1);
printf("Enter second string: ");
scanf("%s", s2);

int m = strlen(s1);
int n = strlen(s2);
int dp[m + 1][n + 1];
int result = 0;

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


for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0)
dp[i][j] = 0;
else if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = 1 + dp[i - 1][j - 1];
result = max(result, dp[i][j]);
} else
dp[i][j] = 0;
}
}

printf("Length of Longest Common Substring: %d\n", result);


return 0;
}

You might also like