Cod sursa(job #789251)

Utilizator paul_gabryelPaul Buda paul_gabryel Data 17 septembrie 2012 18:19:23
Problema Aho-Corasick Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb

#include <cstdio>
#include <fstream>
#include <iostream>
#include <string>

using namespace std;

int p[10001],n,sol;
string a,b,s;

void f ()
{
	for(size_t i=2,q=0;i<b.size();++i)
	{
		for(;q&&b[i]!=b[q+1];q=p[q]);
		if(b[q+1]==b[i])
			++q;
		p[i]=q;
	}
}

int main ()
{
	
	ifstream in ("ahocorasick.in");
	freopen ("ahocorasick.out","w",stdout);
	in>>s>>n;
	a=" "+s;
	for(;n;--n)
	{
		in>>s;
		b=" "+s;
		for(size_t i=1;i<b.size();++i)
			p[i]=0;
		sol=0;
		f();
			for(size_t i=1,q=0;i<a.size();++i)
		{
			for(;q&&a[i]!=b[q+1];q=p[q]);
			if(a[i]==b[q+1])
				++q;
			if(q+1==b.size())
				++sol;
		}
		printf("%d\n",sol);
	}
	
	return 0;
	
}