fork(1) download
  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
stdin
3 3
mais
grande
mundo
mas
grande
mundo
1 5
a
aaaaa
aaaaaa
aaaaaaa
a
aaaaaaaaa
1 1
abc
abc
0 0
stdout
182
9
8