Cod sursa(job #617864)

Utilizator darkseekerBoaca Cosmin darkseeker Data 15 octombrie 2011 12:02:25
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <cstdio>
#include <fstream>
#include <string>
using namespace std;

const int NMAX = 2000005;
const char in[] = "strmatch.in";
const char out[] = "strmatch.out";

int urm[NMAX],m,n;
int matches[1005];
char T[NMAX],P[NMAX];

ifstream fin(in);
ofstream fout(out);

void urmatorul(char *p)
{
	int k=-1,x;
	
	urm[0] = 0;
	for(x=1; x<m; x++)
	{
		while(k>0 && p[k+1] != p[x]) k = urm[k];
		if(p[k+1] == p[x])
			k++;
		urm[x] = k + 1;
	}
}

int main()
{
	fin.get(P,NMAX,'\n');
	fin.get();
	fin.get(T,NMAX,'\n');
	fin.get();
	
	m = strlen(P);
	n = strlen(T);
	
	urmatorul(P);
	
	int i , x = -1, matchesCount = 0;
	
	for(i=0; i<n; i++)
	{
		while(x>0 && P[x+1] != T[i]) x = urm[x];
		if(P[x+1] == T[i]) x++;
		if(x == m-1)
			{
				if(matchesCount < 1000)
				matches[++matchesCount] = i-m+1;
				x = urm[x];
			}
	}
	
	fout<<matchesCount<<'\n';
	for(i=1; i<=matchesCount; i++)
		fout<<matches[i]<<" ";
	fout<<'\n';
	
	fin.close();
	fout.close();
	return 0;
}