Cod sursa(job #728871)

Utilizator costyv87Vlad Costin costyv87 Data 29 martie 2012 02:20:42
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <cstdio>
#include <string.h>
#include <vector>
using namespace std;
#define nm 2000010
vector <int> c;
FILE *f,*g;
char s1[nm],s2[nm];
int urm[nm],sol=0,m,i;

void pas1() {
int i,k;
s1[0]='0';
fscanf(f,"%s",s1+1);

for (urm[1]=0,k=0,i=2,m=strlen(s1)-1;i<=m;i++) {
	while (k>0 && s1[k+1]!=s1[i]) k=urm[k];
	if (s1[k+1]==s1[i]) k++;
	urm[i]=k;
	}	
}

void pas2() {
int i,k,n;
s2[0]='0';
fscanf(f,"%s",s2+1);

for (k=0,n=strlen(s2)-1,i=1;i<=n;i++) {
	while (k>0 && s1[k+1]!=s2[i]) k=urm[k];
	if (s1[k+1]==s2[i]) k++;
	if (k==m) {
		if (c.size()<1000)
			c.push_back(i-m);
		}
	}


}

int main() {
f=fopen("strmatch.in","r");
g=fopen("strmatch.out","w");

pas1(); //creare urm
pas2(); //rezolvarea propriu-zisa

fprintf(g,"%d\n",c.size());
for (i=0;i<c.size();i++)
	fprintf(g,"%d ",c[i]);

fclose(g);
return 0;
}