Cod sursa(job #2103736)

Utilizator dragos.galeteanu2001Dragos Iulian dragos.galeteanu2001 Data 10 ianuarie 2018 19:07:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#define minim(a, b) ((a < b) ? a : b)
#define limit 2000005

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int aa, bb;
char a[limit], b[limit];
int rep[limit], index[1024];

void prefix_maker()
{
	int i, nr_same = 0;
	for (i = 2, rep[1] = 0; i <= aa; i++) {
		while (nr_same && a[nr_same + 1] != a[i]) nr_same = rep[nr_same];
		if (a[nr_same + 1] == a[i]) nr_same++;
		rep[i] = nr_same;
	}
}

int main()
{
	int i, same = 0, nr = 0;
	f >> a;
	f.get();
	f >> b;
	f.get();

	for (; (a[aa] >= 'A' && a[aa] <= 'Z') || (a[aa] >= 'a' && a[aa] <= 'z') || (a[aa] >= '0' && a[aa] <= '9'); aa++);
	for (; (b[bb] >= 'A' && b[bb] <= 'Z') || (b[bb] >= 'a' && b[bb] <= 'z') || (b[bb] >= '0' && b[bb] <= '9'); bb++);

	for (i = aa; i; i--) a[i] = a[i - 1]; a[0] = ' ';
	for (i = bb; i; i--) b[i] = b[i - 1]; b[0] = ' ';

	prefix_maker();

	for (i = 1; i <= bb; i++) {
		while (same && a[same + 1] != b[i]) same = rep[same];
		if (a[same + 1] == b[i]) same++;
		if (same == aa) {
			same = rep[aa];
			nr++;
			if (nr <= 1000) index[nr] = i - aa;
		}
	}

	g << nr << '\n';
	for (i = 1; i <= minim(nr, 1000); i++) g << index[i] << ' ';
    return 0;
}