Cod sursa(job #1117117)

Utilizator dspMihaiDespotovici Mihai dspMihai Data 23 februarie 2014 02:15:23
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <fstream>
#include <cstring>
#include <cstdio>
using namespace std;
 
char crt;
char a[2000001], b[2000001];
int urmator[2000001], c[2000001];
int i,j,M,N,nr;
 
/*
void initurm() 
{ 
    long i, j;
    urmator[0] = -1; 
    for(i = 0, j = -1; i < N; i++, j++, urmator[i] = j) 
        while(j >= 0 && a[i] != a[j])
            j = urmator[j]; 
} 
 
void kmp() 
{ 
    long i,j;
    for (i=0, j=0; i<M; i++,j++)
    {
        while (j>=0 and a[j]!=b[i])
            j=urmator[j];
        if (j==N-1) 
            c[nr++]=i-N+1;
    }
}
*/

int main ()
{
    /*FILE *f, *g;
    f=fopen("strmatch.in", "r");
    g=fopen("strmatch.out", "w");
    fscanf(f, "%c", &crt);
    while (crt!='\n')
    {
        a[N++]=crt;
        fscanf(f, "%c", &crt);
    }
    fscanf(f, "%c", &crt);
    while (crt!='\n')
    {
        b[M++]=crt;
        fscanf(f, "%c", &crt);
    }
*/
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	f>>a;
	f.get();
	f>>b;
	f.close();
	N=strlen(a)-1;
	M=strlen(b)-1;
    urmator[0] = -1; 
    for(i = 1, j = 0; i < N; ++i, ++j, urmator[i] = j) 
        while(j > -1 && a[i] != a[j])
            j = urmator[j]; 
         
	  
	 for(i = 0, j = 0; i < M; ++i, ++j) 
	 {
		while(j > -1 && b[i] != a[j]) 
		   j = urmator[j]; 
		if (j==N-1) 
		{
			if (nr<1000) c[nr]=i-N+1;
			++nr;
		}
	}
	 
	g<<nr<<"\n";
	if (nr>1000) nr=1000;
    for (i=0; i<nr; ++i) g<<c[i]<<" ";
	g<<"\n";
   /* fprintf(g, "%d\n", nr);
	if (nr>1000) nr=1000;
    for (i=0; i<nr; ++i) fprintf(g, "%d ", c[i]);
    fclose(f); fclose(g);*/
    return 0;
}