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
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include "message.h"
using namespace std;

int wynik[3][100005];
int ile[3][100005];
pair<int, int> para;
pair<int, int> p1,p2,p3;

pair<int,int> MIN(pair<int,int> a, pair<int,int> b, pair<int,int> c)
{
	return min(a,min(b,c));
	}

int main()
{
	ios_base::sync_with_stdio(0);
	int n, m;
	string a, b;
	
	if(MyNodeId()==0)
	{
		cin >> n >> m;
		cin >> a >> b;
		a='%'+a;
		b='#'+b;
		for(int i=1; i<=max(n,m); i++)
		{
			wynik[1][i]=i;
			}
			
		for(int x=1; x<=m; x++)
		{
			wynik[2][0]=x;
			for(int y=1; y<=n; y++)
			{
				if(a[y]==b[x])
				{
					p1=make_pair(wynik[1][y-1], ile[1][y-1]);
					p2=make_pair(wynik[2][y-1]+1, ile[2][y-1]);
					p3=make_pair(wynik[1][y]+1, ile[1][y]);
					para=MIN(p1,p2,p3);
					wynik[2][y]=para.first;
					ile[2][y]=para.second;
					}
				else
				{
					if(int(a[y])<int(b[x])) p1=make_pair(wynik[1][y-1]+1, ile[1][y-1]+1);
					else p1=make_pair(wynik[1][y-1]+1, ile[1][y-1]);
					p2=make_pair(wynik[2][y-1]+1, ile[2][y-1]);
					p3=make_pair(wynik[1][y]+1, ile[1][y]);
					para=MIN(p1,p2,p3);
					wynik[2][y]=para.first;
					ile[2][y]=para.second;
					}	
				}
			for(int y=0; y<=n; y++)
			{
				wynik[1][y]=wynik[2][y];
				ile[1][y]=ile[2][y];
				wynik[2][y]=0;
				ile[2][y]=0;
				}	
			}	
	
		cout << wynik[1][n] << " " << ile[1][n] << endl;
	
		}
	
	return 0;
}