Cod sursa(job #1442615)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 25 mai 2015 22:06:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 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;
						           if(nr<=1000) sol[nr]=i-2*n-1;
						          }
						 }
}

void afisare(){
	 int i,limit;
	 
	 fo<<nr<<"\n";
	 
	 if(nr<=1000) limit=nr;
	 else limit=1000;
	 
	 for(i=1;i<=limit;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;
}