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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include "message.h"

using namespace std;

int n, m;
int tab[100005];
int tab2[100005];
char S1[100005];
char S2[100005];
int szerokosc[105];
int dlugosc[105];
int startSZ[105];
int startDL[105];

vector < pair <int, int> > v1, v2;

pair <int, int> PP (pair <int, int> F, pair <int, int> S)
{
	if (F < S) return F;
	return S;
}

bool rozproszony ()
{
	int moj_numer = MyNodeId();
	int liczba_instancji = NumberOfNodes();
	if (liczba_instancji > m) liczba_instancji = m;
	if (liczba_instancji > n) liczba_instancji = n;
	if (moj_numer >= liczba_instancji) return 0;
	for (int i = 0; i < liczba_instancji; ++i) szerokosc[i] = m / liczba_instancji;
	for (int i = 0; i < (m % liczba_instancji); ++i) szerokosc[i]++;
	for (int i = 0; i < liczba_instancji; ++i) dlugosc[i] = n / liczba_instancji;
	for (int i = 0; i < (n % liczba_instancji); ++i) dlugosc[i]++;
	startSZ[0] = 0;
	for (int i = 1; i <= liczba_instancji; ++i) startSZ[i] = startSZ[i - 1] + szerokosc[i - 1];
	startDL[0] = 0;
	for (int i = 1; i <= liczba_instancji; ++i) startDL[i] = startDL[i - 1] + dlugosc[i - 1];
	v1.clear();
	for (int i = 0; i <= szerokosc[moj_numer]; ++i) v1.push_back(make_pair(startSZ[moj_numer] + i, 0));
	for (int i = 0; i < liczba_instancji; ++i)
	{
		if (moj_numer == 0)
		{
			for (int j = 1; j <= dlugosc[i]; ++j) tab[j] = startDL[i] + j;
			for (int j = 1; j <= dlugosc[i]; ++j) tab2[j] = 0;
		}
		else
		{
			Receive(moj_numer - 1);
			for (int j = 1; j <= dlugosc[i]; ++j)
			{
				tab[j] = GetInt(moj_numer - 1);
				tab2[j] = GetInt(moj_numer - 1);
			}
		}
		for (int j = 1; j <= dlugosc[i]; ++j)
		{
			v2.clear();
			v2.push_back(make_pair(tab[j], tab2[j]));
			for (int k = 1; k <= szerokosc[moj_numer]; ++k)
			{
				if (S1[startDL[i] + j] == S2[startSZ[moj_numer] + k])
				{
					v2.push_back(PP(PP(v1[k - 1], make_pair(v1[k].first + 1, v1[k].second)), make_pair(v2[k - 1].first + 1, v2[k - 1].second)));
				}
				else if (S1[startDL[i] + j] > S2[startSZ[moj_numer] + k])
				{
					v2.push_back(PP(PP(make_pair(v1[k - 1].first + 1, v1[k - 1].second), make_pair(v1[k].first + 1, v1[k].second)), make_pair(v2[k - 1].first + 1, v2[k - 1].second)));
				}
				else
				{
					v2.push_back(PP(PP(make_pair(v1[k - 1].first + 1, v1[k - 1].second + 1), make_pair(v1[k].first + 1, v1[k].second)), make_pair(v2[k - 1].first + 1, v2[k - 1].second)));
				}
			}
			v1.clear();
			for (int k = 0; k <= szerokosc[moj_numer]; ++k) v1.push_back(v2[k]);
			if (moj_numer != liczba_instancji - 1)
			{
			    PutInt(moj_numer + 1, v1[szerokosc[moj_numer]].first);
			    PutInt(moj_numer + 1, v1[szerokosc[moj_numer]].second);
			}
		}
		if (moj_numer != liczba_instancji - 1) Send(moj_numer + 1);
	}
	if (moj_numer == liczba_instancji - 1) printf("%d %d\n", v1[szerokosc[moj_numer]].first, v1[szerokosc[moj_numer]].second);
	return 0;
}

int main ()
{
	scanf("%d%d",&n,&m);
	gets(S1);
	gets(S1 + 1);
	gets(S2 + 1);
	rozproszony();
	return 0;
}