fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
  5. #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
  6. #define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
  7. #define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
  8. #define SZ(S) ((int) ((S).size()))
  9.  
  10. #define DEBUG(x) { cout << #x << " = " << x << endl; }
  11. #define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; }
  12. #define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; }
  13.  
  14. int cnt[2][311];
  15. int n[2];
  16.  
  17. struct Node {
  18.     int child[26];
  19. } nodes[2][100111];
  20. int nNode[2];
  21.  
  22. int dfs(int t, int u) {
  23.     int res = 1;
  24.     REP(c,26) {
  25.         if (nodes[t][u].child[c]) {
  26.             res += dfs(t, nodes[t][u].child[c]);
  27.             if (u) ++cnt[t][c];
  28.         }
  29.     }
  30.     return res;
  31. }
  32.  
  33. int main() {
  34.     ios :: sync_with_stdio(false); cin.tie(NULL);
  35.     cout << (fixed) << setprecision(6);
  36.     while (cin >> n[0] >> n[1] && n[0]) {
  37.         memset(cnt, 0, sizeof cnt);
  38.         memset(nodes, 0, sizeof nodes);
  39.  
  40.         nNode[0] = nNode[1] = 1;
  41.         REP(turn,2) {
  42.             REP(i,n[turn]) {
  43.                 string a; cin >> a;
  44.                 if (turn == 1) reverse(a.begin(), a.end());
  45.  
  46.                 int p = 0;
  47.                 for(char c : a) {
  48.                     if (!nodes[turn][p].child[c - 'a']) {
  49.                         nodes[turn][p].child[c - 'a'] = nNode[turn]++;
  50.                     }
  51.                     p = nodes[turn][p].child[c - 'a'];
  52.                 }
  53.             }
  54.         }
  55.  
  56.         long long res = 0;
  57.         res += (dfs(0, 0) - 1LL) * (dfs(1, 0) - 1LL);
  58.         REP(c,26) res -= cnt[0][c] * cnt[1][c];
  59.         cout << res << endl;
  60.     }
  61.     return 0;
  62. }
  63.  
  64.  
Success #stdin #stdout 0.02s 23816KB
comments (?)
stdin
copy 
3 3
mais
grande
mundo
mas
grande
mundo
1 5
a
aaaaa
aaaaaa
aaaaaaa
a
aaaaaaaaa
1 1
abc
abc
0 0
stdout
copy 
182
9
8
https://ideone.com/MpKN1N
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!