50216. 3 Strings LCS
難度：3.5/5
沒教你怎麼看的話這題就有5了。
Second Try: 3/5 Used Time: 10:591
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <ctype.h>
#include <limits.h>
#define min(a,b) ((a)<(b)?(a):(b))
static inline int max(int a, int b){
return a > b ? a : b;
}
int dfs(char* a, char* b, char* c){
if(a[0] == '\0' || b[0] == '\0' || c[0] == '\0'){
return 0;
}
else{
if(a[0] == b[0] && b[0] == c[0]) return 1 + dfs(a + 1, b + 1, c + 1);
int nums[4];
char *temp_a, *temp_b, *temp_c;
temp_b = b, temp_c = c;
while(*temp_b != '\0' && *temp_b != a[0]) temp_b++;
while(*temp_c != '\0' && *temp_c != a[0]) temp_c++;
if(*temp_b == '\0' || *temp_c == '\0') nums[0] = 0;
else nums[0] = 1 + dfs(a + 1, temp_b + 1, temp_c + 1);
temp_a = a, temp_c = c;
while(*temp_a != '\0' && *temp_a != b[0]) temp_a++;
while(*temp_c != '\0' && *temp_c != b[0]) temp_c++;
if(*temp_a == '\0' || *temp_c == '\0') nums[1] = 0;
else nums[1] = 1 + dfs(temp_a + 1, b + 1, temp_c + 1);
temp_a = a, temp_b = b;
while(*temp_a != '\0' && *temp_a != c[0]) temp_a++;
while(*temp_b != '\0' && *temp_b != c[0]) temp_b++;
if(*temp_a == '\0' || *temp_b == '\0') nums[2] = 0;
else nums[2] = 1 + dfs(temp_a + 1, temp_b + 1, c + 1);
nums[3] = dfs(a + 1, b + 1, c + 1);
return max(max(nums[0], nums[1]), max(nums[2], nums[3]));
}
}
int main(){
char a[20] = {'\0'}, b[20] = {'\0'}, c[20] = {'\0'};
while(scanf("%s %s %s", a, b, c) == 3){
printf("%d\n", dfs(a, b, c));
}
}