Cod sursa(job #2516071)

Utilizator Narcis09Grecu Narcis Narcis09 Data 30 decembrie 2019 12:14:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <cstring>
#define dmax 2000001
using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

char a[dmax], b[dmax];
int prefix[dmax], n, m;
int poz[1001], k;

void crp(){
	int i, j=0;
	prefix[1]=0;
	for (i=2;i<=n;i++){
		while (j>0&&a[j+1]!=a[i])
			j=prefix[j];
		if (a[j+1]==a[i])
			++j;
		prefix[i]=j;
	}
}

void kmp(){
	int i, j=0;
	for (i=1;i<=m;i++){
		while (j>0&&a[j+1]!=b[i])
			j=prefix[j];
		if (a[j+1]==b[i])
			++j;
		if (j==n){
			++k;
			if (k<=1000) poz[k]=i-j;
			j=prefix[j];
		}
	}
	cout<<k<<endl;
	k=min(k, 1000);
	for (i=1;i<=k;i++)
		cout<<poz[i]<<" ";
}

int main()
{
	cin>>(a+1);
	cin.get();
	cin>>(b+1);
	a[0]=b[0]=' ';
	int i;
	n=strlen(a)-1, m=strlen(b)-1;
	crp();
	kmp();
	cin.close();
	cout.close();
	return 0;
}