10100 - Longest Match

[gr81]

Hi,

run it again with input you provided, getting same response as you mentioned without any change in code.
code is at same place http://ideone.com/jLH1FX# with test case 40/41 newly added.

Thanks.

[brianfry713]

Your code doesn't match the output if there is a trailing space on the last line.

[messiNayan]

Why I am getting wrong answer:
my code:

Code: Select all

#include<stdio.h>
#include<string.h>
int l[1001][1001];
char s[1001];
char t[1001];
int max(int, int);
int findlcs(int, int);
char* find_path(int, int, int);
void initialize(char*, int);
int main(void)
{
	//freopen("in.txt", "r", stdin);
	char *parser;
	memset(s, 0, sizeof(s));
	memset(t, 0, sizeof(t));
	int caseNo = 0;
	while (gets(s) != NULL)
	{
		gets(t);
		caseNo++;
		if (caseNo < 10)
			printf(" %d. ", caseNo);
		else
			printf("%d. ", caseNo);
		int m = strlen(s);
		int n = strlen(t);
		if (m == 0 || n == 0)
			printf("Blank!\n");
		else
		{
			initialize(s, m);
			initialize(t, n);
			int index = findlcs(m, n);
			char *path = find_path(index, m, n);
			int cnt = 0;
			parser = strtok(path," ");
			while (parser != NULL)
			{
				cnt++;
				parser = strtok(NULL," ");
			}
			printf("Length of longest match: %d\n",cnt);
			path = NULL;
			memset(s, 0, sizeof(s));
			memset(t, 0, sizeof(t));

		}
	
	}
	//fclose(stdin);
	//while (1);
	return 0;
}

void initialize(char *a, int m)
{
	for (int i = 0; i < m; i++)
	{
		if (!((a[i] >= 65 && a[i] <= 90) || (a[i] >= 'a' && a[i] <= 'z') || (a[i] >= '0' && a[i] <= '9')))
			a[i] = 32;

	}
}
char* find_path(int index, int m, int n)
{
	char path[1000];
	path[index] = '\0';
	int i = m, j = n;
	while (i > 0 && j > 0)
	{
		if (s[i - 1] == t[j - 1])
		{
			path[index - 1] = s[i - 1];
			i--;
			j--;
			index--;

		}
		else if (l[i - 1][j] > l[i][j - 1])
			i--;
		else
			j--;
	}
	return path;

}
int findlcs(int m, int n)
{
	memset(l, 0, sizeof(l));
	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (s[i - 1] == t[j - 1])
				l[i][j] = 1 + l[i - 1][j - 1];
			else l[i][j] = max(l[i][j - 1], l[i - 1][j]);
		}
	}
	return l[m][n];

}
int max(int a, int b)
{
	if (a > b)
		return a;
	return b;
}

[brianfry713]

Don't return the address of a local variable in your find_path function.

[messiNayan]

http://ideone.com/O9F7IB
I have fixed what you mentioned(Not to return the address of local variable from find_path).But still wrong answer.Can you tell me the input case for which my code fails.

[brianfry713]

Try input:
bob ate cake
bob likes cake