Cod sursa(job #1532885)

Utilizator hasmasandragosHasmasan Dragos hasmasandragos Data 21 noiembrie 2015 18:51:27
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <string.h>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
const int pat=2000005;
char P[pat],A[pat];
int Z[pat];
int k,n1,n2,sol;
int l,r;
int kp,beta;
int lung, p1, p2;

int main()
{
	P[0]='.';
	fi>>P+1;
	n1=strlen(P+1);
	strcat(P,"$");
	fi.get();
	fi>>A;
	strcat(P,A);
	Z[0]=Z[1]=0;
	l=r=0;
	n2=strlen(P+1);
	for (k=2;k<=n2;k++)
	{
		// se determina Z[k] si se actualizeaza l si r
		if (r<k)
		{
			p1=1;
			p2=k;
			lung=0;
			while (P[p1]==P[p2])
			{
				lung++;
				p1++;
				p2++;
			}
			if (lung==0)
				Z[k]=0;
			else
			{
				Z[k]=lung;
				l=k;
				r=p2-1;
			}
		}
		else
		{
			kp=k-l+1;
			beta=r-k+1;
			if (Z[kp]<beta)
				Z[k]=Z[kp];
			else
			{
				p2=r+1;
				p1=beta+1;
				lung=0;
				while (P[p1]==P[p2])
				{
					lung++;
					p1++;
					p2++;
				}
				Z[k]=beta+lung;
				l=k;
				r=p2-1;
			}
		}
	}
	for (int i=n1+2;i<=n2;i++)
		if (Z[i]==n1)
			sol++;
	fo<<sol<<'\n';
	for (int i=n1+2;i<=n2;i++)
		if (Z[i]==n1)
			fo<<i-n1-2<<" ";
	fi.close();
	fo.close();
	return 0;
}