Cod sursa(job #2051697)

Utilizator DACSTEPStepan Dacian DACSTEP Data 29 octombrie 2017 13:57:15
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <string.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char S[2000005],T[2000005];
int n,m,Z[2000005],v[2000005],t;
void calcul(int m, char S[], int Z[])
{
	int L,R,k,kp,beta;
	Z[1]=0;
	L=R=1;
	for (k=2;k<=m;k++)
		if (S[k]!=S[1])
			Z[k]=0;
		else
			if (k>R)
			{
				Z[k]=1;
				while (S[k+Z[k]]==S[1+Z[k]])
					Z[k]++;
				L=k;
				R=k+Z[k]-1;
			}
			else
			{
				kp=k-(L-1);
				beta=R-(k-1);
				Z[k]=min(Z[kp],beta);
				while (S[k+Z[k]]==S[1+Z[k]])
					Z[k]++;
				if(k+Z[k]-1>R)
				{
					L=k;
					R=k+Z[k]-1;
				}
			}
}

int main()
{
	f>>S+1;
	n=strlen(S+1);
	strcat(S+1,"$");
	f>>T;
	strcat(S+1,T);
	m=strlen(S+1);
	calcul(m,S,Z);
	for (int i=1;i<=m;i++)
		if(Z[i]==n)
        {
            t++;
            v[t]=i;
        }
    g<<t<<endl;
    if(t<1000)
    for(int i=1;i<=t;i++)
        g<<v[i]-n-2<<' ';
        else
           for(int i=1;i<=1000;i++)
        g<<v[i]-n-2<<' ';
	return 0;
}