Cod sursa(job #1492853)

Utilizator mr.koboldKo Bold mr.kobold Data 28 septembrie 2015 12:10:22
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.13 kb
#include <stdio.h>
#include <stdlib.h>

int main()
{
	FILE *input = fopen("cmlsc.in", "r");
	FILE *output = fopen("cmlsc.out", "w");

	long n, m;
	long *a, *b;

	long base_a, base_b;
	long *c;
	long common_index;
	long check_fwd;
	bool found;
	bool finally_over = false;

	fscanf(input, "%ld %ld", &n, &m);

	a = (long*)malloc(n*sizeof(long));
	b = (long*)malloc(m*sizeof(long));
	c = (long*)malloc((n + m) / 2 * sizeof(long));

	for (long i = 0; i < n; i++)
		fscanf(input, "%ld", &a[i]);

	for (long i = 0; i < m; i++)
		fscanf(input, "%ld", &b[i]);

	common_index = 0;
	base_a = 0;
	base_b = 0;
	found = false;
	while (base_a < n && base_b < m && !finally_over)
	{
		found = false;
		for (check_fwd = 0; !found && (base_a + check_fwd < n || base_b + check_fwd < m) && !finally_over; check_fwd++)
		{
			for (int i = 0; i <= check_fwd && !found && !finally_over; i++)
			{
				if (base_a + i < n && base_b + check_fwd < m && a[base_a + i] == b[base_b + check_fwd])
				{
					c[common_index] = a[base_a + i];
					//printf("%ld, ", c[common_index]);
					common_index++;
					found = true;
					base_a += (i + 1);
					base_b += (check_fwd + 1);
				}
				else
				{
					if (base_a + check_fwd < n && base_b + i < m)
					{
						if (a[base_a + check_fwd] == b[base_b + i])
						{
							c[common_index] = a[base_a + check_fwd];
							//printf("%ld, ", c[common_index]);
							common_index++;
							found = true;
							base_a += (i + 1);
							base_b += (check_fwd + 1);
						}
						finally_over = true;
					}

				}
				if (!(base_a + check_fwd < n || base_b + check_fwd < m))
				{
					if (a[base_a + check_fwd] == b[base_b + check_fwd])
					{
						c[common_index] = a[base_a + check_fwd];
						//printf("%ld, ", c[common_index]);
						common_index++;
						found = true;
						base_a += (i + 1);
						base_b += (check_fwd + 1);
						finally_over = true;
					}
				}
			}

		}
	}

	fprintf(output, "%ld\n", common_index);
	for (long i = 0; i < common_index; i++)
		fprintf(output, "%ld ", c[i]);

	//printf("\nDone...\nPress any key");
	getchar();

	return 0;
}