Cod sursa(job #348481)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 15 septembrie 2009 21:08:10
Problema Potrivirea sirurilor Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <fstream>

using namespace std;

#define fin  "strmatch.in"
#define fout "strmatch.out"

#define NMAX 2000100

char a[NMAX], b[NMAX];
int pi[NMAX];

void prefix(char a[], int pi[])
{
	int i, pos;

	pi[ 1 ] = 0;
	pos = 0;

	for ( i = 2; a[i]; ++i )
	{
		while ( pos > 0 && a[pos+1] != a[i] )
			pos = pi[pos];
		if ( a[pos+1] == a[i] )
			++pos;
		pi[i] = pos;
	}
}

int kmp(char model[], char str[], int pif[])
{
	int i, pos, ret = 0;

	pos = 0;
	for ( i = 1; str[i]; ++i )
	{
		while ( pos > 0 && model[ pos + 1 ] != str[i] )
			pos = pif[pos];
		if ( model[ pos + 1 ] == str[i] )
			++pos;
		if ( model[ pos + 1 ] == 0 )
			str[i - pos + 1] = 1, pos = pi[pos], ++ret;
	}

	return ret;
}

int main()
{
	int cnt = 0;

	freopen(fin,"r",stdin);
	freopen(fout,"w",stdout);

	cin >> a+1 >> b+1;

	prefix(a,pi);

	cout << kmp(a,b,pi) << endl;
	for ( int i = 1; b[i] && cnt < 1000; ++i )
		if ( b[i] == 1 )
			cout << i - 1 << " ", ++cnt;

	return 0;
}