Cod sursa(job #328256)

Utilizator c_e_manuEmanuel Cinca c_e_manu Data 1 iulie 2009 13:49:03
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<fstream>
#include<cstring>
#include<algorithm>
#define MaxN 1000005
#define MaxM 50005
#define MaxL 25

using namespace std;

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

char B[MaxN],A[MaxL];
int pi[MaxN],pos[MaxN],N,M,n,k;
bool ok[MaxN];

void prefix(char A[])
{	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(char A[],char B[])
{	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, MaxL);
		N=strlen(A);
		for(i=N+1;i;i--) A[i]=A[i-1];
		A[0]=' ';
		prefix(A);
		KMP(A,B);
		for(i=0;i<=N;i++) A[i]='\0';
	}
	sort(pos+1,pos+1+n);
	k=0;  
	for(i=1;i<=n;i++)   
		ok[pos[i]]=1;  
    for(i=0;i<=M;i++)  
		if(ok[i]) k++;  
	fout<<k;  
    return 0;
}