Cod sursa(job #1442612)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 25 mai 2015 22:01:12
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<fstream>
#include<cstring>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");

const int MAX_L = 2*2000006;
const int MAX_SOL = 1005;

int nr,sol[MAX_SOL];
int n,m,p[MAX_L];
char a[MAX_L];

void kmp(char *a, const int &n, const int &m){
	 int i,k,lung=n+m+1;
	 p[1]=0;
	 k=0;
	 
	 for(i=2;i<=lung;i++){
	                      while(k>0 && a[k+1]!=a[i]) k=p[k];
	                      if(a[k+1]==a[i]) k++;
	                      p[i]=k;
	                      if(k==n && nr<=1000) sol[++nr]=i-2*n-1;
						 }
}

void afisare(){
	 int i;
	 fo<<nr<<"\n";
	 for(i=1;i<=nr;i++) fo<<sol[i]<<" ";
}

int main(){
	fi>>(a+1); n = strlen(a+1);
	a[n+1]='$';
	fi>>(a+n+2); m = strlen(a+n+2);
	
	kmp(a,n,m);
	afisare();
	
	fi.close();
	fo.close();
	return 0;
}