Cod sursa(job #2057715)

Utilizator WebDesignbyTMGhiorghiu Ioan-Viorel WebDesignbyTM Data 4 noiembrie 2017 17:28:03
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#define DM 2000005
#include <cstdio>
using namespace std;

FILE * fi = fopen("strmatch.in", "r");
FILE * fo = fopen("strmatch.out", "w");
char s[DM], t[DM], c;
int p[DM], n, m, v[DM], k, cnt;

void getp()
{
	k = 0;
	for (int i = 2; i <= n; ++i)
	{
		while (k && s[k+1] != s[i])
			k = p[k];
		if (s[k+1] == s[i])
			++k;
		p[i] = k;
	}
}

void solve()
{
	k = 0;
	for (int i = 1; i <= m; ++i)
	{
		while (k && s[k+1] != t[i])
			k = p[k];
		if (s[k+1] == t[i])
			++k;
		if (k == n)
		{
			++cnt;
			if (cnt <= 1000)
				v[cnt] = i - n;
			k = p[k];
		}
	}
}

int main()
{
	c = getc(fi);
	while (c != '\n')
	{
		s[++n] = c;
		c = getc(fi);
	}
	c = getc(fi);
	while (c != EOF)
	{
		t[++m] = c;
		c = getc(fi);
	}
	getp();
	solve();
	fprintf(fo, "%d\n", cnt);
	(cnt > 1000) ? cnt = 1000:cnt = cnt;
	for (int i = 1; i <= cnt; ++i)
		fprintf(fo, "%d ", v[i]);
	return 0;
}