Cod sursa(job #1075369)

Utilizator Lucian-GeorgeFMI Popa Lucian George Lucian-George Data 8 ianuarie 2014 21:47:08
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;

int pref[2000001];
char A[2000001],B[2000001];
int main()
{
	int i,j,poz,ok,p,l,nr=0,t[10001];
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	f>>A>>B;
	l=strlen(A);
	for (i=1; i<l; i++)
	{
		for (j=1; j<=i; j++)
		{
			poz=0;
			ok=1;
			for (p=j; p<=i; p++)
			{
				if (A[p]!=A[poz])
				{
					ok=0;
					p=i+1;
				}
				poz++;
			}
			if (ok) 
			{
				pref[i]=i-j+1;
				j=i+1;
			}
		}
		if (ok==0) pref[i]=0;
	}
	//for (i=0; i<l; i++) cout<<pref[i]<<" ";
	//cout<<endl;
	poz=0;
	for (i=0; i<strlen(B); i++)
	{
		if (poz==l)
		{
			//cout<<i-poz<<" ";
			t[++nr]=i-poz;
			poz=pref[poz-1];
		}
		if (A[poz]!=B[i]) poz=pref[poz-1];
		else poz++;
	}
	if (poz==l) t[++nr]=i-poz;
	g<<nr<<"\n";
	if (nr<1000) for (i=1; i<=nr; i++) g<<t[i]<<" ";
	else for (i=1; i<=1000; i++) g<<t[i]<<" ";
	return 0;
}