Pagini recente » Cod sursa (job #919531) | Cod sursa (job #197464) | Cod sursa (job #117642) | Cod sursa (job #1995228) | Cod sursa (job #2313284)
// By Stefan Radu
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <string>
#include <cctype>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <map>
#include <set>
using namespace std;
#define sz(x) (int)(x).size ()
typedef pair < int, int > pii;
typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;
ifstream cin ("ahocorasick.in");
ofstream cout ("ahocorasick.out");
class Aho {
public:
Aho () {
root = new Node ();
cin >> s >> n;
coresp.resize (n);
for (int i = 0; i < n; ++ i) {
string aux;
cin >> aux;
coresp[i] = this -> mAdd (aux);
}
this -> mSetLinks();
}
void Solve () {
auto curNode = root;
for (int i = 0; i < sz (s); ++ i) {
while (curNode != root) {
if (curNode -> nxt[s[i] - 'a']) break;
curNode = curNode -> sLink;
}
if (curNode -> nxt[s[i] - 'a']) {
curNode = curNode -> nxt[s[i] - 'a'];
++ curNode -> frecv;
}
}
while (not stk.empty ()) {
curNode = stk.top ();
stk.pop ();
curNode -> sLink -> frecv += curNode -> frecv;
}
for (int i = 0; i < n; ++ i) {
cout << coresp[i] -> frecv << '\n';
}
}
private:
struct Node {
Node () {
this -> frecv = 0;
this -> sLink = nullptr;
for (int i = 0; i < 26; ++ i) this -> nxt[i] = nullptr;
}
int frecv;
Node *nxt[26], *sLink;
};
int n;
string s;
Node *root;
stack < Node* > stk;
vector < Node* > coresp;
Node* mAdd (string s) {
Node* cur = root;
for (int i = 0; i < sz (s); ++ i) {
if (not cur -> nxt[s[i] - 'a']) {
cur -> nxt[s[i] - 'a'] = new Node ();
}
cur = cur -> nxt[s[i] - 'a'];
}
return cur;
}
void mSetLinks () {
queue < Node* > q;
root -> sLink = root;
for (int i = 0; i < 26; ++ i) {
if (not root -> nxt[i]) continue;
root -> nxt[i] -> sLink = root;
q.push (root -> nxt[i]);
}
while (not q.empty ()) {
auto curNode = q.front ();
stk.push (curNode);
q.pop ();
for (int i = 0; i < 26; ++ i) {
if (not curNode -> nxt[i]) continue;
auto sLink = curNode -> sLink;
while (sLink != root) {
if (sLink -> nxt[i]) break;
sLink = sLink -> sLink;
}
if (sLink -> nxt[i]) {
curNode -> nxt[i] -> sLink = sLink -> nxt[i];
}
else {
curNode -> nxt[i] -> sLink = root;
}
q.push (curNode -> nxt[i]);
}
}
}
};
int main () {
Aho *aC = new Aho ();
aC -> Solve ();
}