-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path11081_strings_DP.c
71 lines (57 loc) · 1.57 KB
/
11081_strings_DP.c
1
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/*
* Name: chen rushan
* mail: [email protected]
* uva: 11081
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_N_CHARS 60
int count[2][MAX_N_CHARS + 1][MAX_N_CHARS + 1];
void
DP(char *s1, char *s2, char *s3)
{
int l1 = strlen(s1), l2 = strlen(s2), l3 = strlen(s3);
int b1 = 0, b2 = 0, b3 = 0;
/* initialize */
for (b1 = 0; b1 <= l1; ++b1) {
for (b2 = 0; b2 <= l2; ++b2) {
count[l3 & 1][b1][b2] = 1;
}
}
for (b3 = l3 - 1; b3 >= 0; --b3) {
for (b1 = l1; b1 >= 0; --b1) {
for (b2 = l2; b2 >= 0; --b2) {
/* count the ways to construct s3[b3:l3] from
* s1[b1:l1] and s2[b2:l2] */
int n1 = 0, n2 = 0, i = 0;
/* search in subspace 1 */
for (i = b1; i < l1; ++i) {
if (s1[i] == s3[b3]) {
n1 += count[(b3 + 1) & 1][i + 1][b2];
}
}
/* search in subspace 2 */
for (i = b2; i < l2; ++i) {
if (s2[i] == s3[b3]) {
n2 += count[(b3 + 1) & 1][b1][i + 1];
}
}
count[b3 & 1][b1][b2] = (n1 + n2) % 10007;
}
}
}
}
int
main(int argc, char **argv)
{
int N = 0;
char s1[MAX_N_CHARS + 1], s2[MAX_N_CHARS + 1], s3[MAX_N_CHARS + 1];
scanf("%d", &N);
while (N--) {
scanf("%s%s%s", s1, s2, s3);
DP(s1, s2, s3);
printf("%d\n", count[0][0][0]);
}
return 0;
}