154 lines
2.8 KiB
C++
154 lines
2.8 KiB
C++
#include <cstdio>
|
|
#include <iostream>
|
|
#include <queue>
|
|
#include <math.h>
|
|
#include <cstring>
|
|
|
|
const int MAXS = 500000;
|
|
const int MAXC = 26;
|
|
|
|
|
|
int out[MAXS];
|
|
int f[MAXS];
|
|
int g[MAXS][MAXC];
|
|
|
|
int build_string_matcher(std::string arr[], int k) {
|
|
std::memset(out, 0, sizeof out);
|
|
std::memset(g, -1, sizeof g);
|
|
|
|
int states = 1;
|
|
|
|
for (int i = 0; i < k; ++i)
|
|
{
|
|
const std::string &word = arr[i];
|
|
int currentState = 0;
|
|
|
|
for (int j = 0; j < word.size(); ++j)
|
|
{
|
|
int ch = word[j] - 'a';
|
|
|
|
|
|
if (g[currentState][ch] == -1)
|
|
g[currentState][ch] = states++;
|
|
|
|
currentState = g[currentState][ch];
|
|
}
|
|
|
|
out[currentState] |= (1 << i);
|
|
}
|
|
|
|
for (int ch = 0; ch < MAXC; ++ch)
|
|
if (g[0][ch] == -1)
|
|
g[0][ch] = 0;
|
|
|
|
std::memset(f, -1, sizeof f);
|
|
|
|
std::queue<int> q;
|
|
|
|
for (int ch = 0; ch < MAXC; ++ch)
|
|
{
|
|
if (g[0][ch] != 0)
|
|
{
|
|
f[g[0][ch]] = 0;
|
|
q.push(g[0][ch]);
|
|
}
|
|
}
|
|
|
|
while (q.size())
|
|
{
|
|
int state = q.front();
|
|
q.pop();
|
|
|
|
for (int ch = 0; ch <= MAXC; ++ch)
|
|
{
|
|
if (g[state][ch] != -1)
|
|
{
|
|
int failure = f[state];
|
|
|
|
while (g[failure][ch] == -1)
|
|
failure = f[failure];
|
|
|
|
failure = g[failure][ch];
|
|
f[g[state][ch]] = failure;
|
|
|
|
out[g[state][ch]] |= out[failure];
|
|
|
|
q.push(g[state][ch]);
|
|
}
|
|
}
|
|
}
|
|
|
|
return states;
|
|
}
|
|
|
|
int find_next_state(int currentState, char nextInput)
|
|
{
|
|
int answer = currentState;
|
|
int ch = nextInput - 'a';
|
|
|
|
|
|
while (g[answer][ch] == -1)
|
|
answer = f[answer];
|
|
|
|
return g[answer][ch];
|
|
}
|
|
|
|
void search_words(std::string queries[], int k, std::string text) {
|
|
build_string_matcher(queries, k);
|
|
|
|
int current_state = 0;
|
|
|
|
int counts[k];
|
|
|
|
std::memset(counts, 0, sizeof counts);
|
|
|
|
for (int i = 0; i < text.size(); i++) {
|
|
current_state = find_next_state(current_state, text[i]);
|
|
|
|
if (out[current_state] == 0)
|
|
continue;
|
|
|
|
for (int j = 0; j < k; j++) {
|
|
if (out[current_state] & (1 << j)) {
|
|
counts[j]++;
|
|
}
|
|
}
|
|
}
|
|
|
|
for (int i = 0; i < k; i++) {
|
|
std::printf("%d\n", counts[i]);
|
|
}
|
|
}
|
|
|
|
|
|
int main() {
|
|
int N, Q;
|
|
std::string S, query;
|
|
|
|
std::scanf("%d %d", &N, &Q);
|
|
|
|
char c_s[N];
|
|
std::fscanf(stdin, "%s", c_s);
|
|
S = c_s;
|
|
|
|
std::string queries[Q];
|
|
int i = 0;
|
|
int q_copy = Q;
|
|
char c_query[3000];
|
|
while(q_copy != 0) {
|
|
|
|
std::fscanf(stdin, "%s", c_query);
|
|
query = c_query;
|
|
queries[i] = query;
|
|
|
|
i++;
|
|
q_copy--;
|
|
}
|
|
|
|
search_words(queries, Q, S);
|
|
|
|
return 0;
|
|
}
|
|
|
|
|