Cod sursa(job #408362)

Utilizator alex@ndraAlexandra alex@ndra Data 2 martie 2010 23:36:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <stdio.h>
#include<string.h>
using namespace std;

#define millions 2000001
#define thousand 1001

char P[millions], T[millions];
int prefx[millions], D[thousand];

int n, m;


void found(int d)
{
	
	D[0]++;

	if (D[0] <= 1000)
	{
		
		D[D[0]] = d;
	}
}


void citire()
{
	freopen("strmatch.in", "r", stdin);

	P[0] = T[0] = ' ';
	gets(P+1);
	gets(T+1);
}


void prefix(char P[])
{
	int p, k;
	prefx[1] = 0;

	for (p = 2; p <= m; p++)
	{

		k = prefx[p-1];
        while (k > 0 && P[k+1] != P[p])
		{
		  k = prefx[k];
		}

	
		if (P[k+1] == P[p])
		{
			
			k = k+1;
		}

		prefx[p] = k;
	}
}


void knuth_morris_pratt(char P[], char T[])
{
	int t, k;

	prefix(P);

	for (k = 0, t = 1; t <= n; ++t)
	{
		while (k > 0 && P[k+1] != T[t])
		{
			k = prefx[k];
		}

		if (P[k+1] == T[t])
		{
			k = k+1;
		}

		if (k == m)
		{
			found(t-m);
			k = prefx[k];
		}
	}
}
	
 void afisare()
{
	int i;
	freopen("strmatch.out", "w", stdout);
    	printf("%d\n", D[0]);

	for (i = 1; i <= 1000 && i <= D[0]; ++i)
		printf("%d ", D[i]);
}

int main()
{

	citire();

     for (m = -1; P[m+1]; ++m);
     for (n = -1; T[n+1]; ++n);

    knuth_morris_pratt(P, T);

	
	afisare();
	return 0;
}