Cod sursa(job #578419)

Utilizator costyv87Vlad Costin costyv87 Data 11 aprilie 2011 11:52:24
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 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);
m=strlen(s1)-1;
n=strlen(s2)-1;
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==m) {
		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;
}