Cod sursa(job #302788)

Utilizator floringh06Florin Ghesu floringh06 Data 9 aprilie 2009 12:05:05
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <cstdio>
#include <cstring>

using namespace std;

#define FIN "strmatch.in"
#define FOUT "strmatch.out"
#define MAX_N 2000005

char A[MAX_N], P[MAX_N];
int U[MAX_N];
int S[1 << 10];
int N, M, cnt;

	void prefix ()
	{
		int k = 0, i;
		
		for (i = 2; i <= M; ++i)
		{
			while (k > 0 && P[k + 1] != P[i]) k = U[k];
			if (P[k + 1] == P[i]) ++k;
			U[i] = k;
		}
	}

	int main ()
	{
		freopen (FIN, "r", stdin);
		freopen (FOUT, "w", stdout);
		
		gets (P + 1);
		gets (A + 1);
		N = strlen (A + 1), M = strlen (P + 1);
		prefix ();
		
		int i, k = 0;
		for (i = 1; i <= N; ++i)
		{
			while (k > 0 && P[k + 1] != A[i]) k = U[k];
			if (P[k + 1] == A[i]) ++k;
			
			if (k == M && cnt < 1000)
				S[++cnt] = i - M;
			else 
				if (k == M) ++cnt;
		}
		printf ("%d\n", cnt);
		for (i = 1; i <= cnt && i <= 1000; ++i)
			printf ("%d ", S[i]);
	}