Pagini recente » Cod sursa (job #1662002) | Profil StarGold2 | Cod sursa (job #2108370) | Cod sursa (job #459848) | Cod sursa (job #1122589)
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
class Automaton {
public:
static const int NIL = -1;
Automaton(const int _sigma = 0, const int _v = 0, const int _start = NIL):
sigma(_sigma),
v(_v),
start(_start),
delta(vector< vector<int> >(_v, vector<int>(_sigma, NIL))),
terminal(vector<bool>(_v, false)) {}
int Size() const {
return v;
}
int Sigma() const {
return sigma;
}
int Start() const {
return start;
}
int Delta(const int x, const int symbol) const {
return delta[x][symbol];
}
bool IsTerminal(const int x) const {
return terminal[x];
}
vector<int> GetTerminal() const {
vector<int> terminalStates;
for (int x = 0; x < v; ++x)
if (terminal[x])
terminalStates.push_back(x);
return terminalStates;
}
void SetTerminal(const int x) {
terminal[x] = true;
}
int AddVertex() {
delta.push_back(vector<int>(sigma, NIL));
terminal.push_back(false);
return v++;
}
void AddEdge(const int from, const int to, const int symbol) {
delta[from][symbol] = to;
}
protected:
int sigma, v, start;
vector< vector<int> > delta;
vector<bool> terminal;
};
class AhoCorasickAutomaton: public Automaton {
public:
AhoCorasickAutomaton(const int _sigma, const vector< vector<int> > &signatures):
Automaton(_sigma, 1, 0),
signatureCount(int(signatures.size())),
pi(vector<int>(1, 0)),
signatureIndices(vector< vector<int> >(1, vector<int>())),
processingOrder(vector<int>()) {
for (int i = 0, x; i < int(signatures.size()); ++i) {
x = start;
for (int j = 0; j < int(signatures[i].size()); x = delta[x][signatures[i][j++]]) {
if (delta[x][signatures[i][j]] == NIL) {
AddEdge(x, AddVertex(), signatures[i][j]);
pi.push_back(0);
signatureIndices.push_back(vector<int>());
}
}
signatureIndices[x].push_back(i);
}
queue<int> q;
for (q.push(start); !q.empty(); q.pop()) {
int x = q.front();
processingOrder.push_back(x);
for (int symbol = 0; symbol < sigma; ++symbol) {
int currentPi = pi[x];
for (; currentPi != start && delta[currentPi][symbol] == NIL; currentPi = pi[currentPi]);
if (delta[currentPi][symbol] != NIL && delta[currentPi][symbol] != delta[x][symbol])
currentPi = delta[currentPi][symbol];
if (delta[x][symbol] == NIL) {
delta[x][symbol] = currentPi;
} else {
pi[delta[x][symbol]] = currentPi;
q.push(delta[x][symbol]);
}
}
}
reverse(processingOrder.begin(), processingOrder.end());
}
vector<int> GetFrequencies(const vector<int> &stringToSearch) const {
vector<int> signatureFrequencies = vector<int>(signatureCount, 0), vertexFrequencies = vector<int>(v, 0);
for (int i = 0, x = start; i < int(stringToSearch.size()); ++i)
++vertexFrequencies[x = delta[x][stringToSearch[i]]];
for (int i = 0; i + 1 < v; ++i)
vertexFrequencies[pi[processingOrder[i]]] += vertexFrequencies[processingOrder[i]];
for (int x = 0; x < v; ++x)
for (vector<int>::const_iterator index = signatureIndices[x].begin(); index != signatureIndices[x].end(); ++index)
signatureFrequencies[*index] += vertexFrequencies[x];
return signatureFrequencies;
}
private:
int signatureCount;
vector<int> pi;
vector< vector<int> > signatureIndices;
vector<int> processingOrder;
};
string String;
vector<string> Signatures;
vector<int> Frequence;
void Solve() {
vector< vector<int> > signatures = vector< vector<int> >(int(Signatures.size()), vector<int>());
for (int i = 0; i < int(Signatures.size()); ++i)
for (int j = 0; j < int(Signatures[i].size()); ++j)
signatures[i].push_back(int(Signatures[i][j] - 'a'));
AhoCorasickAutomaton A = AhoCorasickAutomaton(26, signatures);
vector<int> stringToSearch;
for (int i = 0; i < int(String.size()); ++i)
stringToSearch.push_back(int(String[i] - 'a'));
Frequence = A.GetFrequencies(stringToSearch);
}
void Read() {
ifstream cin("ahocorasick.in");
int n;
cin >> String >> n;
Signatures = vector<string>(n, "");
for (int i = 0; i < n; ++i)
cin >> Signatures[i];
cin.close();
}
void Print() {
ofstream cout("ahocorasick.out");
for (int i = 0; i < int(Signatures.size()); ++i)
cout << Frequence[i] << "\n";
cout.close();
}
int main() {
Read();
Solve();
Print();
return 0;
}