/home/toolbox/public_html/solutions/104/10405/recursive.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 cnt;
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 /* length passed in is where to check, a -1 means done */
74 int ret = 0;
75
76 DEBUG printf("lcs (%d:%s) (%d:%s)\n", s1, l1, s2, l2);
77 if ((0 <= s1) && (0 <= s2))
78 {
79 /* both strings still have something to look at */
80 if (l1[s1] == l2[s2])
81 {
82 /* found a match */
83 ret = 1 + lcs((s1 - 1), (s2 - 1));
84 } /* found a match */
85 else
86 {
87 /* not a match -- so try each side */
88 ret = mx( lcs(s1-1,s2), lcs(s1,s2-1) );
89 } /* not a match -- so try each side */
90 } /* both strings still have something to look at */
91 cnt++;
92 return ret;
93 } /* FUNCTION lcs */
94
95 void process()
96 {
97 /* FUNCTION process */
98 int len1;
99 int len2;
100 int res;
101
102 len1 = strlen(l1) - 1;
103 len2 = strlen(l2) - 1;
104 printf("(%d:%s) (%d:%s)\n", len1, l1, len2, l2);
105 cnt = 0;
106 res = lcs(len1, len2);
107 printf("(cnt:%d) ", cnt);
108 printf("%d\n", res);
109 } /* FUNCTION process */
110
111 int main()
112 {
113 /* main */
114 int moreToDo;
115
116 init();
117 moreToDo = getInput();
118 while (moreToDo)
119 {
120 /* while */
121 process();
122 moreToDo = getInput();
123 } /* while */
124
125 return EXIT_SUCCESS;
126 } /* main */
127