Cod sursa(job #2304770)

Utilizator AlexPascu007Pascu Ionut Alexandru AlexPascu007 Data 18 decembrie 2018 16:33:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
#include <cstring>
#define DIM 2000010
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int i,l,p[DIM],sol,v[DIM],n,m;
char a[DIM],b[DIM];
void precalculare() {
	l=0; p[1]=0;
	for (i=2;i<=n;i++) {
		while (l!=0&&b[i]!=b[l+1])
			l=p[l];
		if (b[i]==b[l+1])
			l++;
		p[i]=l;
	}
}
int main() {
	fin>>b+1; n=strlen(b+1);
	fin>>a+1; m=strlen(a+1);
	precalculare();
	l=0;
	for (i=1;i<=m;i++) {
		while (l!=0&&a[i]!=b[l+1])
			l=p[l];
		if (a[i]==b[l+1])
			l++;
		if (l==n) {
			sol++;
			if (sol<=1000)
				v[sol]=i-l+1;
			l=p[l];
		}
	}
	fout<<sol<<"\n";
	for (i=1;i<=min(1000,sol);i++)
		fout<<v[i]-1<<" ";
	return 0;
}