Cod sursa(job #535820)

Utilizator ooctavTuchila Octavian ooctav Data 17 februarie 2011 20:04:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <cstdio>
#include <cstring>
#define NMAX 2000010
#define MMAX 2000010
#define MOD1 100003
#define MOD2 100019
#define P 122
#define FOR(i, a, b)	for(int i = a ; i <= b ; i++)
int P1 = 1, P2 = 1;

int URM[MMAX];
char A[NMAX],B[MMAX];
int M, N;
int NR = 0;
int poz[NMAX];
int L[NMAX];

void citire()
{
	gets(A + 1);
	gets(B + 1);
	M = strlen(A + 1);
	while(!A[M] || A[M] == '\n' || A[M] == EOF)
		M--;
	N = strlen(B + 1);
	while(!B[N] || B[N] == '\n' || B[N] == EOF)
		N--;
}

void face_l()
{
	int k;
	FOR(i, 2, M)
	{
		k = L[i - 1];
		while(k && A[k + 1] != A[i])
			k = L[k];
		if(A[k + 1] == A[i])
			k++;
		L[i] = k;
	}
}

void comp()
{
	int k = 0;
	FOR(i, 1, N)
	{
		while(k && A[k + 1] != B[i])
			k = L[k];
		if(A[k + 1] == B[i])
			k++;
		if(k == M)
			poz[++NR] = i - M;
	}
}

void scrie()
{
	printf("%d\n",NR);
	for(int i = 1 ; i <= NR && i <= 1000 ; i++)
		printf("%d ",poz[i]);
}

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	citire();
	face_l();
	comp();
	scrie();
	return 0;
	
}