Cod sursa(job #1088925)

Utilizator NicuCJNicu B. NicuCJ Data 20 ianuarie 2014 23:13:12
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <fstream>
using namespace std;
int n, k, pr[2000001], i, m, rez[1001], nr;
char a[2000001], b[2000001];
int main()
{
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	f.getline(a+1, 1000);
	f.getline(b+1, 1000);
	n=strlen(a+1);
	m=strlen(b+1);
	k=0;
	pr[1]=0;
	for(i=2; i<=n; i++)
	{
		while(k>0 && a[k+1]!=a[i])
			k=pr[k];
		if(a[k+1]==a[i])
			k++;
		pr[i]=k;
	}
	k=0;
	for(i=1; i<=m; i++)
	{
		while(k>0 && a[k+1]!=b[i])
			k=pr[k];
		if(a[k+1]==b[i])
			k++;
		if(k==n)
		{
			k=pr[n];
			nr++;
			if(nr<=1000)
			rez[nr]=i-n+1;
		}
	}
	g<<nr<<"\n";
	for(i=1; i<=min(1000, nr); i++)
	{
		g<<rez[i]-1<<" ";
	}
}