Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- struct node{
- struct node* word[26];
- bool end;
- ~node(){
- delete[] word;
- }
- };
- node *p, *s;
- int add(string &s, node* root){
- node* current = root;
- int ans = 0;
- for(int i = 0; i < s.size(); i++){
- int letter = s[i]-'a';
- if(current->word[letter] == NULL) {
- ans++;
- current->word[letter] = new node();
- }
- //cout << "ola\n";
- current = current->word[letter];
- }
- current->end = true;
- return ans;
- }
- ll prefixos, cutl[26];
- void cut(node* no, int h){
- for(int i = 0; i < 26; i++){
- if(no->word[i] == NULL) continue;
- if(h) cutl[i]++;
- cut(no->word[i], h + 1);
- }
- }
- ll solve(node* no, int h){
- ll ans = 0;
- if(h) ans = prefixos;
- for(int i = 0; i < 26; i++){
- if(no->word[i] == NULL) continue;
- if(h) ans -= cutl[i];
- ans += solve(no->word[i], h + 1);
- }
- return ans;
- }
- int main(){
- ios::sync_with_stdio(false);
- cin.tie(NULL);
- while(true){
- int qp, qe; cin >> qp >> qe;
- if((qp+qe) == 0) break;
- s = new node();
- p = new node();
- prefixos = 0;
- memset(cutl, 0, sizeof cutl);
- for(int i = 0; i < qp; i++){
- string aux; cin >> aux;
- prefixos += add(aux, p);
- }
- for(int i = 0; i < qe; i++){
- string aux; cin >> aux;
- reverse(aux.begin(), aux.end());
- add(aux, s);
- }
- cut(p, 0);
- cout << solve(s, 0) << endl;
- //delete s;
- //delete p;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement