Pagini recente » Cod sursa (job #2484504) | Cod sursa (job #1028530) | Cod sursa (job #585021) | Cod sursa (job #1014067) | Cod sursa (job #98476)
Cod sursa(job #98476)
// Liviu Ciortea, Bucuresti, Romania (TopCoder handle: _efer_)
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <utility>
#include <string>
#include <ctime>
using namespace std;
#define REP(i, N) for (int i = 0; i < (N); ++i)
#define REPV(i, a, b) for (int i = (a); i <= (b); ++i)
#define REPD(i, N) for (int i = (N)-1; i >= 0; --i)
#define REPVD(i, b, a) for (int i = (b); i >= (a); --i)
#define REPIT(it, v) for (it = (v).begin(); it != (v).end(); ++it)
#define SZ(a) ((int)(a).size())
#define MP make_pair
#define PB push_back
#define X first
#define Y second
#define ALL(a) (a).begin(), (a).end()
#define CLR(a) memset((a), 0, sizeof(a))
#define MSET(a, v) memset((a), v, sizeof(a))
#define CPY(dest, source) memcpy(dest, source, sizeof(dest))
typedef long long LL;
typedef vector<int> VI;
typedef vector<string> VS;
typedef pair<int, int> PII;
const int MAXL = 32;
const int MAX_TOTAL = 1<<20;
const int MAXS = 10240000;
const int NUM_LETTERS = 3;
char word[MAXL];
char text[MAXS];
// radacina este in nodul 0
int adj[MAX_TOTAL][4], C;
int go[MAX_TOTAL], paps[MAX_TOTAL], ch[MAX_TOTAL];
char terminal[MAX_TOTAL];
void put_tree(int node, char* word, int depth = 0) {
if (*word) {
int nxt = word[0] - 'a';
if (adj[node][nxt] == -1) {
ch[++C] = nxt;
adj[node][nxt] = C;
}
put_tree(adj[node][nxt], word+1, depth+1);
} else {
terminal[node] = 1;
}
}
void build_automaton() {
deque<int> Q;
paps[0] = go[0] = -1;
REP(i, NUM_LETTERS) {
if (adj[0][i] != -1) {
paps[adj[0][i]] = 0;
Q.PB(adj[0][i]);
}
}
while (!Q.empty()) {
int r = Q.front(); Q.pop_front();
int n = paps[r];
while (n && adj[go[n]][ch[r]] == -1) n = go[n];
if (n) go[r] = adj[go[n]][ch[r]];
else go[r] = 0;
REP(i, NUM_LETTERS) {
if (adj[r][i] != -1) {
paps[adj[r][i]] = r;
Q.PB(adj[r][i]);
}
}
}
}
int main() {
//time_t start = clock();
freopen("abc2.in", "rt", stdin);
freopen("abc2.out", "wt", stdout);
scanf("%s", text);
MSET(adj, -1);
while (scanf("%s", word) == 1) put_tree(0, word);
build_automaton();
//fprintf(stderr, "%lf\n", (double)(clock() - start) / CLK_TCK);
int S = strlen(text), n = 0, res = 0;
REPV(i, 1, S) {
int nxt = text[i-1] - 'a';
while (n && adj[n][nxt] == -1) n = go[n];
if (adj[n][nxt] != -1) n = adj[n][nxt];
res += terminal[n];
}
printf("%d\n", res);
//fprintf(stderr, "%lf\n", (double)(clock() - start) / CLK_TCK);
return 0;
}