Cod sursa(job #651817)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 21 decembrie 2011 18:14:47
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<fstream>
#define NMAX 2000100
using namespace std;

char A[NMAX],B[NMAX];
int n,nr,fail[NMAX],sol[1024];

void KMP() {
	int i,q=0;
	for(i=1;B[i];i++) {
		while(q && A[q+1] != B[i])
			q=fail[q];
		if(A[q+1] == B[i])
			q++;
		if(q==n) {
			q=fail[n];
			sol[nr++]=i-n;
			if(nr==1000)
				return;
			}
		}
}
void prefix() {
	int i,q=0;
	fail[1]=0;
	for(i=2;A[i];i++) {
		while(q && A[q+1] != A[i])
			q=fail[q];
		if(A[q+1] == A[i])
			q++;
		fail[i]=q;
		}
	n=i-1;
}	
void citire() {
	ifstream in("strmatch.in");
	in.getline(A+1,NMAX);
	in.getline(B+1,NMAX);
	in.close();
}
void afis() {
	int i;
	ofstream out("strmatch.out");
	out<<nr<<'\n';
	for(i=0;i<nr;i++)
		out<<sol[i]<<' ';
	out<<' ';
	out.close();
}
int main() {
	citire();
	prefix();
	KMP();
	afis();
}