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
#include <bits/stdc++.h>
#include "message.h"
//#include <emmintrin.h>

using namespace std;

#define FORE(it,c)  for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
#define FOR(i,a,b)  for(int i=(a);i<(b);++i)
#define REP(i,a)    FOR(i,0,a)
#define ZERO(m)    memset(m,0,sizeof(m))
#define ALL(x)      x.begin(),x.end()
#define PB          push_back
#define S          size()
#define LL          long long
#define ULL        unsigned long long
#define LD          long double
#define MP          make_pair
#define X          first
#define Y          second
#define VC          vector
#define PII        pair <int, int>
#define VI          VC < int >
#define VVI        VC < VI >
#define VD          VC < double >
#define VVD        VC < VD >
#define VS          VC < string >
#define DB(a)      cerr << #a << ": " << (a) << endl;

template<class T> void print(VC < T > v) {cerr << "[";if (v.S) cerr << v[0];FOR(i, 1, v.S) cerr << ", " << v[i];cerr << "]\n";}
template<class T> string i2s(T x) {ostringstream o; o << x; return o.str(); }
VS splt(string s, char c = ' ') {VS all; int p = 0, np; while (np = s.find(c, p), np >= 0) {if (np != p) all.PB(s.substr(p, np - p)); p = np + 1;} if (p < s.S) all.PB(s.substr(p)); return all;}

const int MIN_BLOCK = 100;
const int MAX_S = 100100;
const int MAX_NODES = 100;

int n, m;
char s0[MAX_S];
char s1[MAX_S];

LL PREV[MAX_S];
LL CUR[MAX_S];
LL TOP[MAX_S];
LL BOT[MAX_S];

int blockID[MAX_NODES][MAX_NODES];
int blockTurn[MAX_NODES][MAX_NODES];
PII blockOrder[MAX_NODES*2][MAX_NODES];

const LL COST_BIG = 1LL << 32;
const LL COST_SMALL = 1;

int main() {
	scanf("%d%d%s%s", &n, &m, s0, s1);
	

	int NODES = NumberOfNodes();
	int ID = MyNodeId();
	int blocksNo = min(NODES, min(n, m) / MIN_BLOCK + 1);
	
	memset(blockOrder, -1, sizeof(blockOrder));
	REP(i, blocksNo) REP(j, blocksNo) {
		blockID[i][j] = i;
		blockTurn[i][j] = i + j;
		blockOrder[blockTurn[i][j]][blockID[i][j]] = MP(i,j);
	}
	
	REP(turn, blocksNo * 2 - 1) {
		PII p = blockOrder[turn][ID];
		if (p.X == -1) continue;
		
		int x0 = (p.X * n) / blocksNo;
		int x1 = ((p.X + 1) * n) / blocksNo;
		int y0 = (p.Y * m) / blocksNo;
		int y1 = ((p.Y + 1) * m) / blocksNo;
		
		if (p.X == 0) {
			FOR(i, y0, y1 + 1) PREV[i - y0] = i * COST_BIG;
		} else if (blockID[p.X-1][p.Y] != ID) {
			int src = Receive(blockID[p.X-1][p.Y]);
			FOR(i, y0, y1 + 1) PREV[i - y0] = GetLL(src);
		} else {
			// nothing
		}
		
		if (p.Y == 0) {
			FOR(i, x0, x1 + 1) TOP[i - x0] = i * COST_BIG;
		} else if (blockID[p.X][p.Y-1] != ID) {
			int src = Receive(blockID[p.X][p.Y-1]);
			FOR(i, x0, x1 + 1) TOP[i - x0] = GetLL(src);
		} else {
			FOR(i, x0, x1 + 1) TOP[i - x0] = BOT[i - x0];
		}
		
		BOT[0] = PREV[y1 - y0];
		FOR(x, x0 + 1, x1 + 1) {
			CUR[0] = TOP[x - x0];
			FOR(y, y0 + 1, y1 + 1) {
				CUR[y - y0] = PREV[y - y0 - 1] + (s0[x-1] == s1[y-1] ? 0 : COST_BIG + (s0[x-1] < s1[y-1]));
				CUR[y - y0] = min(CUR[y - y0], CUR[y - y0 - 1] + COST_BIG);
				CUR[y - y0] = min(CUR[y - y0], PREV[y - y0] + COST_BIG);
			}
			BOT[x - x0] = CUR[y1 - y0];
			memcpy(PREV, CUR, sizeof(LL)*(y1-y0+1));
		}
		
		if (p.X + 1 < blocksNo && blockID[p.X+1][p.Y] != ID) {
			int src = blockID[p.X+1][p.Y];
			FOR(y, y0, y1 + 1) PutLL(src, CUR[y-y0]);
			Send(src);
		}
		
		if (p.Y + 1 < blocksNo && blockID[p.X][p.Y+1] != ID) {
			int src = blockID[p.X][p.Y+1];
			FOR(x, x0, x1 + 1) PutLL(src, BOT[x-x0]);
			Send(src);
		}
		
		if (p.X + 1 == blocksNo && p.Y + 1 == blocksNo) {
			cout << (CUR[y1 - y0] / COST_BIG) << ' ' << (CUR[y1 - y0] % COST_BIG) << endl;
		}
	}
}