1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <cstdio>
#include <vector>

#include "message.h"

using namespace std;

const int kMaxN = 100000;
const int kMaxM = 100000;
const int kInfinity = kMaxN + kMaxM;

typedef vector<pair<int, int> > Vector;

void Read(vector<char> *v) {
  for (int i = 0; i < v->size(); ++i) {
    (*v)[i] = ' ';
    while ((*v)[i] < 'a' || (*v)[i] > 'z') scanf("%c", &(*v)[i]);
  }
}

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  vector<char> src(n), dst(m);
  Read(&src);
  Read(&dst);

  const int node = MyNodeId();
  const int nodes = NumberOfNodes();

  const int left = (node * m) / nodes;
  const int right = ((node + 1) * m) / nodes;
  const int width = right - left + 1;

  Vector row_0, row_1;
  row_0.resize(width, make_pair(kInfinity, kInfinity));
  row_1.resize(width, make_pair(kInfinity, kInfinity));

  Vector *prev = &row_0;
  Vector *curr = &row_1;

  for (int i = 0; i < nodes; ++i) {
    const int top = (i * (n + 1)) / nodes;
    const int bottom = ((i + 1) * (n + 1)) / nodes;
    if (node > 0) Receive(node - 1);
    for (int j = top; j < bottom; ++j) {
      if (node == 0) {
        (*curr)[0] = make_pair(j, 0);
      } else {
        (*curr)[0].first = GetInt(node - 1);
        (*curr)[0].second = GetInt(node - 1);
      }
      for (int k = left; k < right; ++k) {
        pair<int, int> del = (*prev)[k + 1 - left];
        ++del.first;
        pair<int, int> ins = (*curr)[k     - left];
        ++ins.first;
        pair<int, int> rep = (*prev)[k     - left];
        if (j > 0 && src[j - 1] != dst[k]) {
          ++rep.first;
          if (src[j - 1] < dst[k]) ++rep.second;
        }
        (*curr)[k + 1 - left] = min(min(del, ins), rep);
      }
      if (node < nodes - 1) {
        PutInt(node + 1, (*curr)[width - 1].first);
        PutInt(node + 1, (*curr)[width - 1].second);
      }
      swap(prev, curr);
    }
    if (node < nodes - 1) Send(node + 1);
  }
  if (node == nodes - 1)
    printf("%d %d\n", (*prev)[width - 1].first, (*prev)[width - 1].second);

  return 0;
}