Cod sursa(job #309010)

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

using namespace std;

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

struct sir	{
	int begin, end;
};

sir ok[MaxC];
int pi[100],N,M,n,k;
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)
		{	ok[++n].begin=i-q;
			ok[n].end=i+q;
			q=pi[N];
		}
	}
}

int cmp(sir a, sir b)
{	if(a.begin!=b.begin) return a.begin<b.begin;
	return a.end<b.end;
}

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,30);
		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(ok+1,ok+1+n,cmp);
	//for(i=1;i<=n;i++) fout<<ok[i].begin<<' '<<ok[i].end<<'\n';
	//fout<<'\n';
	k=1;
	for(i=2;i<n;i++)
		if(ok[i].begin!=ok[i+1].begin) k++;
		else	if(ok[i].begin==ok[i+1].begin&&ok[i].end!=ok[i+1].end) k++;
	fout<<k<<'\n';
	return 0;
}