Cod sursa(job #330884)

Utilizator szabotamasSzabo Tamas szabotamas Data 11 iulie 2009 21:44:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <cstdlib>

using namespace std;

#define MAX 20000200

char A[MAX], B[MAX];
long n,m,i,k,kp[MAX],res[1002],rr;

void build(){
	kp[0]=0;
	k=0;
	for (i=1; i<n; i++){
		while (k && A[i]!=A[k]){
			k=kp[k-1];
		}
		if (A[i]==A[k]){
			k++;
		}
		kp[i]=k;
	}
}

void calc(){
	k=0;
	for (i=0; i<m; i++){
		while (k && B[i]!=A[k]){
			k=kp[k-1];
		}
		if (B[i]==A[k]){
			k++;
		}
		if (k==n){
			if (res[0]<1000){
				res[0]++;
				res[res[0]]=i-n+1;
			}
			else { 
				rr++;
			}
		}
	}
}

int main(){
	freopen("strmatch.in", "r", stdin);
		scanf("%s ", &A);
		scanf("%s ", &B);
		n=strlen(A);
		m=strlen(B);
	fclose(stdin);
	res[0]=0;
	rr=0;
	build();
	calc();
	freopen("strmatch.out", "w", stdout);
		printf("%ld\n", res[0]+rr);
		for (i=1; i<=res[0]; i++){
			printf("%ld ", res[i]);
		}
	fclose(stdout);
	return 0;
}