Cod sursa(job #631000)

Utilizator DaicuDaicu Alexandru Daicu Data 6 noiembrie 2011 20:11:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include<stdio.h>
#include<string.h>
#include<vector>
#define nmax 2000003
#define min(a,b) a>b? b:a
using namespace std;
//vector <int> sol;
char a[nmax],b[nmax];
int p[nmax],sol[1000];
void kmp_prefix(char *a,int n){
	int k=-1;
	p[0]=-1;
	for(int i=1;i<n;i++){
		while(k>=0 && a[k+1]!=a[i])
			k=p[k+1];
		if(a[k+1]==a[i])
			k++;
		p[i]=k;
		
	}
}


int main(){
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf("%s",&a);
	scanf("%s",&b);
	int n=strlen(a);
	int m=strlen(b);
	kmp_prefix(a,n);
	int k=-1;
	unsigned int j=0,nr=0;
	for(int i=0;i<m;i++){
		while(k>=0 && a[k+1]!=b[i])
			k=p[k];
		if(a[k+1]==b[i])
			k++;
		if(k==n-1){
			++nr;
			if(nr<=1000)
			sol[nr-1]=i-n+1;
		}
	}
	printf("%d\n",nr);
	k=min(nr,1000);
		for(j=0;j<k;j++)
		printf("%d ",sol[j]);
	return 0;
}