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
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include "message.h"
#include <iostream>

using namespace std;

struct Score
{
    int v, sh;
};

bool operator<(const Score& s1, const Score& s2)
{
    return (s1.v == s2.v ? s1.sh < s2.sh : s1.v < s2.v);
}

void leb(int sp, int n, int tp, int m, char* s, char* t, Score** tab)
{
    int i, j;
    Score p1, p2, p3;
    for (i = 1; i <= m; ++i)
    {
        for (j = 1; j <= n; ++j)
        {
            if (t[i-1+tp] == s[j-1+sp]) tab[i][j] = tab[i-1][j-1];
            else
            {
                p1 = tab[i][j-1];
                p1.v += 1;
                p2 = tab[i-1][j-1];
                p2.v += 1;
                p2.sh += (t[i-1+tp] > s[j-1+sp] ? 1 : 0);
                p3 = tab[i-1][j];
                p3.v += 1;
                tab[i][j] = min(p1, min(p2, p3));
            }
        }
    }
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

    //const int MAX = 100000;
    int n, m;
    char *s, *t;
    cin >> n >> m;
    s = new char[n];
    t = new char[m];
    cin >> s;
    cin >> t;

    //cout << s << ' ' << t << endl;

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

    int p = (node * n) / nodes;
    int k = ((node + 1) * n) / nodes;
    int n2 = k - p;
    int p2, k2, m2;

    Score** tab;
    int i, j, iter;
    int vert = (m / nodes) + 2;
    tab = new Score*[vert+1];
    for (i = 0; i <= vert; ++i) tab[i] = new Score[n2+1];
//cout << node << "p1" << endl;
    for (iter = 0; iter < nodes; ++iter)
    {
        if (iter == 0)
        {
            for (j = 0; j <= n2; ++j)
            {
                tab[0][j].v = j+p;
                tab[0][j].sh = 0;
            }
        }
        else
        {
            for (j = 0; j <= n2; ++j)
            {
                tab[0][j] = tab[m2][j];
            }
        }
//cout << node << "p2" << endl;
        p2 = (iter * m) / nodes;
        k2 = ((iter + 1) * m) / nodes;
        m2 = k2 - p2;
//cout << node << "p3" << endl;
        if (node == 0)
        {
            for (i = 0; i <= m2; ++i)
            {
                tab[i][0].v = i;
                tab[i][0].sh = 0;
            }

        }
        else if (m2 > 0)
        {
            Receive(node-1);
            for (i = 1; i <= m2; ++i)
            {
                tab[i][0].v = GetInt(node-1);
                tab[i][0].sh = GetInt(node-1);
            }
        }
//cout << node << "p4" << endl;
        leb(p, n2, p2, m2, s, t, tab);
//cout << node << "p5" << endl;

/*
        cout << node << "," << iter << ": " << endl;
        for (i = 0; i <= m2; ++i)
        {
            for (j = 0; j <= n2; ++j)
            cout << tab[i][j].v << "," << tab[i][j].sh << " ";
            cout << endl;
        }
*/

        if (node < nodes-1 && m2 > 0)
        {
            for (i = 1; i <= m2; ++i)
            {
                PutInt(node+1, tab[i][n2].v);
                PutInt(node+1, tab[i][n2].sh);
            }
            Send(node+1);
        }
    }
//cout << node << "p6" << endl;
    if (node == nodes-1)
    {
        cout << tab[m2][n2].v << ' ' << tab[m2][n2].sh << endl;
    }
}