Cod sursa(job #1893704)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 25 februarie 2017 22:05:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <bitset>
#include <algorithm>
#include <cmath>
#define MaxN 2000005
#define INF 2140000000
using namespace std;
 
FILE*IN,*OUT;

char first[MaxN],second[MaxN];
int Pref[MaxN],N=0,Out[MaxN],Len;
void Precalc_Pref()
{
	Len=strlen(first+1);
	int k=0;
	for(int i=2;i<=Len;i++)
	{
		while(k&&first[k+1]!=first[i])
			k=Pref[k];
		if(first[k+1]==first[i])
			k++;
		Pref[i]=k;
	}
}
void Precalc_D()
{
	int L=strlen(second+1),k=0;
	for(int i=1;i<=L;i++)
	{
		while(k&&first[k+1]!=second[i])
			k=Pref[k];
		if(first[k+1]==second[i])
			k++;
		if(k==Len)
			Out[++N]=i-Len;
	}
}
int main()
{
    IN=fopen("strmatch.in","r");
    OUT=fopen("strmatch.out","w");
	
	fscanf(IN,"%s%s",first+1,second+1);
	Precalc_Pref();
	Precalc_D();
	fprintf(OUT,"%d\n",N);
	for(int i=1;i<=min(N,1000);i++)
		fprintf(OUT,"%d ",Out[i]);
	return 0;
}