#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
struct Node {
char v;
bool end;
vector<Node*> next;
};
Node *get_node(char v) {
Node *node = new Node();
node->v = v; node->end = false;
node->next.resize(26);
return node;
}
void add(Node *h, string s, int idx) {
if (s.size() == idx) {
h->end = true;
return;
}
if (h->next[s[idx] - 'a'] == NULL) {
h->next[s[idx] - 'a'] = get_node(s[idx]);
}
add(h->next[s[idx] - 'a'], s, idx + 1);
}
Node* pre(vector<string> d) {
Node *h = get_node('$');
for (string s : d) {
add(h, s, 0);
}
return h;
}
bool find(Node *h, string s, int idx) {
if (idx == s.size()) return h->end;
if (h->next[s[idx] - 'a'] != NULL) return find(h->next[s[idx] - 'a'], s, idx + 1);
return false;
}
int count(Node *base, Node *h, string s, int idx) {
if (idx == s.size()) return h->end;
int res = 0;
if (h->end) {
res += count(base, base, s, idx);
}
if (h->next[s[idx] - 'a'] != NULL) {
res += count(base, h->next[s[idx] - 'a'], s, idx + 1);
}
return res;
}
int main() {
vector<string> d(9);
d[0] = "st";
d[1] = "ck";
d[2] = "cag";
d[3] = "low";
d[4] = "tc";
d[5] = "rf";
d[6] = "ove";
d[7] = "a";
d[8] = "sta";
Node *h = pre(d);
cout << "Indexing done" << endl;
string s;
cin >> s;
cout << count(h, h, s, 0) << endl;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8dmVjdG9yPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnN0cnVjdCBOb2RlIHsKCWNoYXIgdjsKCWJvb2wgZW5kOwoJdmVjdG9yPE5vZGUqPiBuZXh0Owp9OwoKTm9kZSAqZ2V0X25vZGUoY2hhciB2KSB7CglOb2RlICpub2RlID0gbmV3IE5vZGUoKTsKCW5vZGUtPnYgPSB2OyBub2RlLT5lbmQgPSBmYWxzZTsKCW5vZGUtPm5leHQucmVzaXplKDI2KTsKCXJldHVybiBub2RlOwp9Cgp2b2lkIGFkZChOb2RlICpoLCBzdHJpbmcgcywgaW50IGlkeCkgewoJaWYgKHMuc2l6ZSgpID09IGlkeCkgewoJCWgtPmVuZCA9IHRydWU7CgkJcmV0dXJuOwoJfQoKCWlmIChoLT5uZXh0W3NbaWR4XSAtICdhJ10gPT0gTlVMTCkgewoJCWgtPm5leHRbc1tpZHhdIC0gJ2EnXSA9IGdldF9ub2RlKHNbaWR4XSk7Cgl9CgoJYWRkKGgtPm5leHRbc1tpZHhdIC0gJ2EnXSwgcywgaWR4ICsgMSk7Cn0KCk5vZGUqIHByZSh2ZWN0b3I8c3RyaW5nPiBkKSB7CglOb2RlICpoID0gZ2V0X25vZGUoJyQnKTsKCWZvciAoc3RyaW5nIHMgOiBkKSB7CgkJYWRkKGgsIHMsIDApOwoJfQoJcmV0dXJuIGg7Cn0KCmJvb2wgZmluZChOb2RlICpoLCBzdHJpbmcgcywgaW50IGlkeCkgewoJaWYgKGlkeCA9PSBzLnNpemUoKSkgcmV0dXJuIGgtPmVuZDsKCWlmIChoLT5uZXh0W3NbaWR4XSAtICdhJ10gIT0gTlVMTCkgcmV0dXJuIGZpbmQoaC0+bmV4dFtzW2lkeF0gLSAnYSddLCBzLCBpZHggKyAxKTsKCXJldHVybiBmYWxzZTsKfQoKaW50IGNvdW50KE5vZGUgKmJhc2UsIE5vZGUgKmgsIHN0cmluZyBzLCBpbnQgaWR4KSB7CglpZiAoaWR4ID09IHMuc2l6ZSgpKSByZXR1cm4gaC0+ZW5kOwoKCWludCByZXMgPSAwOwoJaWYgKGgtPmVuZCkgewoJCXJlcyArPSBjb3VudChiYXNlLCBiYXNlLCBzLCBpZHgpOwoJfQoKCWlmIChoLT5uZXh0W3NbaWR4XSAtICdhJ10gIT0gTlVMTCkgeyAKCQlyZXMgKz0gY291bnQoYmFzZSwgaC0+bmV4dFtzW2lkeF0gLSAnYSddLCBzLCBpZHggKyAxKTsKCX0KCglyZXR1cm4gcmVzOwp9CgppbnQgbWFpbigpIHsKCXZlY3RvcjxzdHJpbmc+IGQoOSk7CglkWzBdID0gInN0IjsKCWRbMV0gPSAiY2siOwoJZFsyXSA9ICJjYWciOwoJZFszXSA9ICJsb3ciOwoJZFs0XSA9ICJ0YyI7CglkWzVdID0gInJmIjsKCWRbNl0gPSAib3ZlIjsKCWRbN10gPSAiYSI7CglkWzhdID0gInN0YSI7CgoJTm9kZSAqaCA9IHByZShkKTsKCWNvdXQgPDwgIkluZGV4aW5nIGRvbmUiIDw8IGVuZGw7CglzdHJpbmcgczsKCWNpbiA+PiBzOwoJY291dCA8PCBjb3VudChoLCBoLCBzLCAwKSA8PCBlbmRsOwoJcmV0dXJuIDA7Cn0=