Cod sursa(job #1688977)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 13 aprilie 2016 20:42:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN 2000050

using namespace std;

char a[MAXN], b[MAXN];
int pre[MAXN], n, m, sol[1050], nq;

void prefix()
{
	int pi = 0;
    for (int i = 2; i <= n; i++) {
        while (pi && a[i] != a[pi+1])
			pi = pre[pi];
        if (a[i] == a[pi+1])
			pi++;
        pre[i] = pi;
    }
}

void solutie(int ind)
{
	++nq;
	if (nq <= 1000)
		sol[nq] = ind;
}

void solve()
{
	int pi = 0;
    for (int i = 1; i <= m; i++) {
        while (pi && b[i] != a[pi+1])
			pi = pre[pi];
        if (b[i] == a[pi+1])
			pi++;
        if (pi >= n)
			solutie(i);
    }
}

void afisare()
{
	printf("%d\n", nq);
    for (int i = 1; i <= min(1000, nq); i++)
		printf("%d ", sol[i]-n);
}

int main()
{
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);

	a[0] = b[0] = ' ';
	fgets(a+1, MAXN, stdin);
	n = strlen(a)-1;
	a[n--] = 0;
	fgets(b+1, MAXN, stdin);
	m = strlen(b)-1;
	b[m--] = 0;

	prefix();
	solve();
	afisare();

    return 0;
}