Cod sursa(job #617890)

Utilizator darkseekerBoaca Cosmin darkseeker Data 15 octombrie 2011 12:11:42
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <cstdio>
#include <fstream>
#include <cstring>
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 ;
	}
}*/

void urmatorul(char *p)
{
	int i = 1;
	int j = 0;
	urm[0] = 0;
	while(i < m)
	{
		if(p[j] == p[i])
			{
				urm[i] = j+1;
				i++;
				j++;
			}
		else
			if(j > 0)
				j = urm[j-1];
			else
			{
				urm[i] = 0;
				i++;
			}
	}
	
	//for(i=0; i<m; i++)
		//printf("%d ",urm[i]);
}

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;
}