Cod sursa(job #733133)

Utilizator pascu_iulianPascu Iulian pascu_iulian Data 11 aprilie 2012 15:28:51
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <fstream>
#include <cstring>
#include <string>
using namespace std;

int main(){
	string N,M,aux;
	int n,m,pi[2000002],k;
	int pos[1000],p=0;
	int i,q;
	
	ifstream fin("strmatch.in");
	ofstream fout("strmatch.out");
	
	
	fin>>aux; N=" "+aux;
	fin>>aux; M=" "+aux;
	m=M.size();
	n=N.size();
	
	
	for(pi[1]=0, k=0, i=2; i<=n; i++){
		while(k>0 && N[k+1]!=N[i])
			k=pi[k];
		if(N[k+1]==N[i])
			k++;
		pi[i]=k;
	}
	aux="";
	for(q=0,i=1;i<=m;i++){
		while(q>0 && N[q+1]!=M[i])
			q=pi[q];
		if(N[q+1]==M[i])
			q++;
		if(q+1==n){
			if(p<=1000) 
				pos[p++]=i-n+1;
			else p++;
		}
	}	
		
	
	fout<<	p<<"\n";
	for(i=0; i<p ; i++)
		fout<<pos[i]<<' ';
	return 0;
}