1. C, Axel Fiedler


/* WA */

#include <stdio.h>
#include <string.h>

#define MAX 100
#define MAX_WORDS 100
#define MAX_WORD_LENGTH 30

char wordArray[MAX_WORDS][MAX_WORD_LENGTH];
char text1[MAX_WORDS*MAX_WORD_LENGTH], text2[MAX_WORDS*MAX_WORD_LENGTH];
int index1, index2;
int c[MAX][MAX], b[MAX][MAX];

void LCSlength()
{
int i, j;

memset(c, 0, sizeof(c));

for (i = 1; i <= index1; i++)
{
for (j = index1; j <= index2; j++)
{
if (strcmp(wordArray[i - 1], wordArray[j - 1]) == 0)
{
c[i][j] = c[i - 1][j - 1] + 1;
b[i][j] = 1;
}
else if (c[i - 1][j] >= c[i][j - 1])
{
c[i][j] = c[i - 1][j];
b[i][j] = 2;
}
else
{
c[i][j] = c[i][j - 1];
b[i][j] = 3;
}
}
}
}

void printLCS(int i, int j)
{
if ((i == 0) || (j == 0))
return;

if (b[i][j] == 1)
{
printLCS(i - 1, j - 1);

if (j == index2)
printf("%s\n", wordArray[i - 1]);
else
printf("%s ", wordArray[i - 1]);
}
else if (b[i][j] == 2)
printLCS(i - 1, j);
else
printLCS(i, j - 1);
}

void cutString(char* c, int* i)
{
char* pointer = strtok(c, " \n");
while (pointer != NULL)
{
strcpy(wordArray[(*i)++], pointer);
pointer = strtok(NULL, " \n");
}
}

int main()
{
while (scanf("%[^#]# %[^#]#", text1, text2) == 2)
{
index1 = 0;
cutString(text1, &index1);
index2 = index1;
cutString(text2, &index2);

LCSlength();
printLCS(index1, index2);
}

return 0;
}