/home/toolbox/public_html/solutions/104/10405/a.c
1 #include <stdio.h>
2 #include <string.h>
3 #include <sys/types.h>
4 #include <sys/stat.h>
5 #include <fcntl.h>
6 #include <stdint.h>
7 #include <math.h>
8 #include <stdlib.h>
9
10 #define TRUE (1 == 1)
11 #define FALSE (1 != 1)
12
13 #define DEBUG if (FALSE)
14
15 /*
16 * Author: Isaac Traxler
17 * Date: 2019-01-22
18 * Purpose: fun
19 * Problem: 10405 - Longest Common Subsequence
20 *
21 * see https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/
22 *
23 */
24
25 /*
26 * This template reads lines of data at a time until end of file.
27 */
28
29 #define MAX_LINE 1010
30
31 char l1[MAX_LINE];
32 char l2[MAX_LINE];
33 int x[MAX_LINE][MAX_LINE];
34
35 void init()
36 {
37 /* FUNCTION init */
38 } /* FUNCTION init */
39
40 void dump()
41 {
42 /* FUNCTION dump */
43 } /* FUNCTION dump */
44
45 int getInput()
46 {
47 /* FUNCTION getInput */
48 int dataReadFlag;
49
50 fgets(l1, MAX_LINE, stdin);
51 if (feof(stdin))
52 dataReadFlag = FALSE;
53 else
54 {
55 /* something to read */
56 dataReadFlag = TRUE;
57 l1[strlen(l1)-1] = 0;
58 fgets(l2, MAX_LINE, stdin);
59 l2[strlen(l2)-1] = 0;
60 } /* something to read */
61 return (dataReadFlag);
62 } /* FUNCTION getInput */
63
64 int mx(int i, int j)
65 {
66 /* FUNCTION mx */
67 return ((i > j) ? i : j);
68 } /* FUNCTION mx */
69
70 int lcs(int s1, int s2)
71 {
72 /* FUNCTION lcs */
73 int i;
74 int j;
75
76 for (i=0; i<=s1; i++)
77 {
78 /* for i */
79 for (j=0; j<=s2; j++)
80 {
81 /* for j */
82 if ((0 == i) || (0 == j))
83 {
84 /* set start to 0 */
85 x[i][j] = 0;
86 } /* set start to 0 */
87 else
88 {
89 /* not on top or right */
90 if (l1[i-1] == l2[j-1])
91 {
92 /* char match */
93 DEBUG printf("(i:%d:%s) (j:%d:%s)\n", i, l1, j, l2);
94 x[i][j] = x[i-1][j-1] + 1;
95 } /* char match */
96 else
97 {
98 /* no match */
99 x[i][j] = mx(x[i-1][j], x[i][j-1]);
100 } /* no match */
101 } /* not on top or right */
102 } /* for j */
103 } /* for i */
104 return x[s1][s2];
105 } /* FUNCTION lcs */
106
107 void process()
108 {
109 /* FUNCTION process */
110 int len1;
111 int len2;
112 int res;
113
114 len1 = strlen(l1);
115 len2 = strlen(l2);
116 DEBUG printf("(%d:%s) (%d:%s)\n", len1, l1, len2, l2);
117 res = lcs(len1, len2);
118 printf("%d\n", res);
119 } /* FUNCTION process */
120
121 int main()
122 {
123 /* main */
124 int moreToDo;
125
126 init();
127 moreToDo = getInput();
128 while (moreToDo)
129 {
130 /* while */
131 process();
132 moreToDo = getInput();
133 } /* while */
134
135 return EXIT_SUCCESS;
136 } /* main */
137