Pagini recente » Cod sursa (job #2826704) | Cod sursa (job #429554) | Cod sursa (job #3154352) | Cod sursa (job #1797971) | Cod sursa (job #1385934)
#include <fstream>
#include <cstring>
using namespace std;
ifstream is("ahocorasick.in");
ofstream os("ahocorasick.out");
char A[1000002];
char B[10002];
int PI[1000002];
int N, k, lenB, lenA, Sol;
void BuildPI()
{
k = 0;
for ( int i = 2; i <= lenB; ++i )
{
while ( k > 0 && B[k+1] != B[i] )
k = PI[k];
if ( B[k+1] == B[i] )
k++;
PI[i] = k;
}
}
void CountApp()
{
k = 0;
for ( int i = 1; i <= lenA; ++i )
{
while ( k > 0 && B[k+1] != A[i] )
k = PI[k];
if ( B[k+1] == A[i] )
k++;
if ( k == lenB )
Sol++;
}
}
int main()
{
is >> A+1;
lenA = strlen(A+1);
is >> N;
for ( int i = 1; i <= N; ++i )
{
Sol = 0;
is >> B+1;
lenB = strlen(B+1);
for ( int j = 1; j <= lenB; ++j )
PI[j] = 0;
BuildPI();
CountApp();
os << Sol << '\n';
}
}