Cod sursa(job #726909)

Utilizator dragosnicolaeNicolae Dragos dragosnicolae Data 27 martie 2012 16:56:01
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<stdio.h>
#include<string.h>
#include<vector>
#define maxn 2000005
using namespace std;
char a[maxn],b[maxn];
int urm[maxn],m,n,nr;
vector <int> sol;
void cit(){
	FILE *f;
	f=fopen("strmatch.in","r");
	fgets(a,maxn,f);
	fgets(b,maxn,f);
	fclose(f);
	m=strlen(a);
	n=strlen(b);
	while((a[m-1]<'a'||a[m-1]>'z')&&(a[m-1]<'A'||a[m-1]>'Z')&&(a[m-1]<'0'||a[m-1]>'9'))
		m--;
	a[m]='\0';
	while((b[n-1]<'a'||b[n-1]>'z')&&(b[n-1]<'A'||b[n-1]>'Z')&&(b[n-1]<'0'||b[n-1]>'9'))
		n--;
	b[n]='\0';
}
void urmatorul(){
	int x,k;
	urm[0]=-1;
	k=-1;
	for(x=1;x<m;x++){
		while(k>0&&a[x]!=a[k+1])
			k=urm[k];
		if(a[k+1]==a[x])
			k++;
		urm[x]=k;
	}
}
void kmp(){
	int i,k;
	k=-1;
	for(i=0;i<n;i++){
		while(k>0&&a[k+1]!=b[i])
			k=urm[k];
		if(a[k+1]==b[i])
			k++;
		if(k==m-1){
			nr++;
			if(nr<=1000)
				sol.push_back(i-m+1);
			k=urm[k];
		}
	}
}
void afis(){
	FILE *f;
	f=fopen("strmatch.out","w");
	fprintf(f,"%d\n",nr);
	for(int i=0;i<nr&&i<1000;i++)
		fprintf(f,"%d ",sol[i]);
	fclose(f);
}
int main(){
	cit();
	urmatorul();
	kmp();
	afis();
	return 0;
}