Cod sursa(job #2693345)

Utilizator davidcotigacotiga david davidcotiga Data 5 ianuarie 2021 15:50:25
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.09 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <set>
#include <algorithm>
#include <stack>
#include <vector>
#include <iomanip>
#include <cstdio>
#include <cstring>


using namespace std;

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

#define SIGMA 26
#define NMAX 102
const int MAX_SIZE = 1e6 + 5;
const int WSIZE = 1e4 + 5;

int g[MAX_SIZE][SIGMA];
int f[MAX_SIZE];
int res[MAX_SIZE];

int wordState[NMAX];

vector<int> q;

void getFailure(int state) {
	int curr, suf;

	for (int i = 0; i < SIGMA; ++i) {
		if (g[state][i]) {
			curr = g[state][i];
			suf = f[state];

			while (suf != 1 && !g[suf][i])
				suf = f[suf];

			if (g[suf][i] && g[suf][i] != curr)
				suf = g[suf][i];
			else
				suf = 1;

			f[curr] = suf;
		}
	}
}

void buildTrie(unsigned int n) {
	char word[WSIZE];
	int currState, nextState;
	int c;

	nextState = 2;
	for (int i = 0; i < n; ++i) {
		fin >> word;
		int sizeW = strlen(word);

		currState = 1;

		for (int j = 0; j < sizeW; ++j) {
			c = word[j] - 'a';

			if (!g[currState][c]) {
				g[currState][c] = nextState++;
			}

			currState = g[currState][c];
		}
		wordState[i] = currState;
	}
}

void statesTraversal() {
	q.push_back(1);

	for (int i = 0; i < q.size(); ++i) {
		for (int j = 0; j < SIGMA; ++j)
			if (g[q[i]][j])
				q.push_back(g[q[i]][j]);
	}
}

void calcFailed(char* s, int sizeS) {
	int c;

	f[1] = 1;

	for (int i = 0; i < q.size(); ++i) {
		getFailure(q[i]);
	}

	int currState = 1;

	for (int j = 0; j < sizeS; ++j) {
		c = s[j] - 'a';

		while (currState != 1 && !g[currState][c])
			currState = f[currState];

		if (g[currState][c])
			currState = g[currState][c];

		res[currState]++;
	}

	for (int i = q.size() - 1; i; --i) {
		res[f[q[i]]] += res[q[i]];
	}
}

int main() {
	char s[MAX_SIZE];
	unsigned int n;

	fin >> s;
	int sizeS = strlen(s);

	fin >> n;

	buildTrie(n);

	statesTraversal();

	calcFailed(s, sizeS);

	for (int i = 0; i < n; i++) {
		fout << res[wordState[i]] << "\n";
	}

	return 0;
}