Cod sursa(job #719199)

Utilizator andrey932Andrei andrey932 Data 21 martie 2012 16:15:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define MAXL 2000001

char A[MAXL],B[MAXL];
int f[MAXL],i,j,n,m,nr;
vector<int> rez;

void preg_kmp() {
	int stare;
	f[0]=-1;
	stare=-1;
	for(i=1;i<=m;i++) {
		while ( (stare>=0)&&(A[stare+1]!=A[i]) ) stare=f[stare];		
		if (A[stare+1]==A[i]) f[i]=stare+1;
		else f[i]=-1;
		stare=f[i];
	}
}

int main() {
	fin.getline(A,MAXL);
	fin.getline(B,MAXL);
	for(m=MAXL;A[m]==0;m--) {}
	for(n=MAXL;B[n]==0;n--) {}
	preg_kmp();	
	//for(i=0;i<=m;i++) cout<<f[i]<<" ";
	//cout<<"\n";
	//cout<<A<<"\n"<<B<<"\n";
	//cout<<m<<" "<<n<<"\n";
	nr=0;
	int stare=-1;
	for(i=0;i<=n;i++) {
		while ( (stare>=0) && (A[stare+1]!=B[i]) ) stare=f[stare];
		if (A[stare+1]==B[i]) stare++;		
		if (stare==m) {
			nr++;
			if (rez.size()<1000) rez.push_back(i-m);
		}
		//cout<<B[i]<<"("<<i<<")"<<"  "<<A[stare]<<"("<<stare<<")"<<"\n";
	}
	fout<<nr<<"\n";
	for(i=0;i<rez.size();i++) fout<<rez[i]<<" ";
	fout<<"\n";
	fout.close();
	return 0;
}