5792 Live Archive

diccionario.cpp

using namespace std;
#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>

#define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
#define For(i, a, b) for (int i=(a); i<(b); ++i)
#define D(x) cout << #x " is " << x << endl

const int MAXN = 100005;

struct trie {
    int size; 
    int g[MAXN][30];
    
    trie (){
        clear();
    }
     
    void clear(){
        size = 0;
        for (int i = 0; i < 30; i++) g[0][i] = -1;
    }
    
    void insert( const string &s){
        int curr = 0;
        for (int i = 0; i < s.size(); i++){
            int c = s[i] - 'a';
            if (g[curr][c] == -1){
                size++;
                g[curr][c] = size;
                for (int j = 0; j < 30; j++)
                    g[size][j] = -1;
            }
            curr = g[curr][c];
        }
    }
};

trie prefix, suffix;
long long cnt [30];

long long suffix_dfs(int node, int level){
    long long ans = 0;
    for (int i = 0; i < 26; i++){
        int next = suffix.g[node][i]; 
        if (next == -1) continue;
        if (level + 1 != 1) cnt[i]++;
        else ans++;
        ans += suffix_dfs(next, level + 1);
    }
    return ans;
} 

long long prefix_dfs(int node, bool first){
    long long ans = 0;
    for (int i = 0; i < 26; i++){
        int next = prefix.g[node][i];
        // Si no tengo ese hijo, puedo poner el sufijo a menos que esté en el nodo vacío
        if (next == -1){
            ans += first ? 0 : cnt[i];
            continue;
        }
        ans += prefix_dfs(next, false);
    }
    return ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    int s, p;
    while (cin >> p >> s){
        if (s == 0 and p == 0) break;
        
        prefix.clear(); suffix.clear();
        
        for (int i = 0; i < p; i++){
            string str;
            cin >> str;
            prefix.insert(str);
        }
        
        for (int i = 0; i < s; i++){
            string str;
            cin >> str;
            reverse(str.begin(), str.end());
            suffix.insert(str);
        }
        
        for (int i = 0; i < 26; i++) cnt[i] = 0LL;
        long long ones = suffix_dfs(0, 0);
        long long ans = prefix_dfs(0, true) + prefix.size * ones;
        cout << ans << endl;
    }
    return 0;
}