Cod sursa(job #309028)

Utilizator c_e_manuEmanuel Cinca c_e_manu Data 29 aprilie 2009 13:07:09
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<fstream>
#include<cstring>
#define MaxN 10000005
#define MaxC 50005

using namespace std;

ifstream fin("abc2.in");
ofstream fout("abc2.out");

int pi[MaxC],N,M,n,k,pos[MaxN];
char A[MaxC],B[MaxN];

void prefix()
{	int i,q=0;
	for(i=2,pi[1]=0;i<=N;i++)
	{	while(q&&A[i]!=A[q+1])
			q=pi[q];
		if(A[i]==A[q+1])q++;
		pi[i]=q;
	}
}

void KMP()
{	int i,q=0;
	for(i=1;i<=M;i++)
	{	while(q&&A[q+1]!=B[i])
			q=pi[q];
		if(A[q+1]==B[i]) q++;
		if(q==N)
		{	q=pi[N];
			n++;
			pos[n]=i-N;
		}
	}
}

int main()
{	int i;
	fin.getline(B,MaxN);
	M=strlen(B);
	for(i=M+1;i;i--) B[i]=B[i-1];
	B[0]=' ';
	while(!fin.eof())
	{	fin.getline(A,MaxC);
		N=strlen(A);
		for(i=N;i;i--) A[i]=A[i-1];
		A[0]=' ';
		prefix();
		KMP();
		for(i=0;i<=N;i++)A[i]='\0';
	}
	sort(pos+1,pos+1+n);
	k=0;i=1;
	while(i<n)
	{	while(pos[i]==pos[i+1]) i++;
		while(pos[i]!=pos[i+1]){i++;k++;}
	}
	fout<<k;
	return 0;
}