Cod sursa(job #578404)

Utilizator costyv87Vlad Costin costyv87 Data 11 aprilie 2011 11:43:12
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <cstdio>
#include <string.h>
#include <vector>
using namespace std;
FILE *f,*g;
vector <int> v;
char s1[2000100],s2[2000100];
int urm[2000100];
int i,k,n,m;

void urmat() {
int i,k;

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

}

int main () {
f=fopen("strmatch.in","r");
g=fopen("strmatch.out","w");
fgets(s1,2000100,f);
fgets(s2,2000100,f);
fclose(f);

s1[strlen(s1)-1]='\0';

m=strlen(s1);
n=strlen(s2);
urmat();

k=0;
for (i=0;i<n;i++) {
	while (k>0 && s1[k]!=s2[i]) 
		k=urm[k-1];
	if (s1[k]==s2[i]) 
		k++;
	if (k==strlen(s1)) {
		if (v.size()<1000) 
			v.push_back(i-m+1);
		k=urm[k-1];
		}
	}
fprintf(g,"%d\n",v.size());
for (vector<int>::iterator j=v.begin();j<v.end();j++) {
	fprintf(g,"%d ",*j);
	}

fclose(g);
return 0;
}