163. 最長子序列

Task Description
最長子序列
給定兩組正整數 a 和 b，其中 a 為 m 位數、b 為 n 位數。 a 和 b 中每個數字 (digit) 視為一個元素，也就是 a 有 m 個元素、 b 有 n 個元素。子序列定義為在母序列出現過且順序一致，舉例如下：
{123} ∈ {{1}、{2}、{3}、{12}、{13}、{23}、{123}}
最長共同子序列定義為出現在每一個序列 (亦即：每個序列都有的值) 且長度最為最長。例如，a=12345、b=1356，最長共同子序列為135，長度為3。請找出a、b 最長共同子序列的長度。

Hint

int_to_array : 將整數的每一位存入陣列中
lcs : 找最長子序列

lcs.h

打上 function header 以及相關的設定。

int lcs(int*, int*, int, int);
void int_to_array(int*, int, int);

lcs.c

撰寫程式碼後對應上傳。

#include "lcs.h"
 
int lcs(int* text1, int* text2, int m, int n) {
    // add your code
}
void int_to_array(int* array1, int value, int index) {
    // add your code
}

main.c

這個檔案無法更改也無須上傳。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#include "lcs.h"
 
int main() {
    int ans = 0;
    int text1[100] = { 0 };
    int text2[100] = { 0 };
    int t1, t2, m, n;
 
    scanf("%d", &m);
    scanf("%d", &n);
    scanf("%d", &t1);
    scanf("%d", &t2);
 
    int_to_array(text1, t1, m);
    int_to_array(text2, t2, n);
    ans = lcs(text1, text2, m, n);
    printf("%d", ans);
    return 0;
}

Input Format

輸入的第一列為 𝑚、𝑛，第二列為 𝑎、𝑏。 Note: 0<m、n≤10、0≤a、b≤2147483647

Output Format

輸出為 a 和 b 的最長共同子序列的長度。

Sample Input

1
2
5 4
12345 1625

Sample Output

1
3

Sample Input

1
2
9 6
112233445 987143

Sample Output

1
2