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

char s1[100002];
char s2[100002];
pair<int, int> v[2][100001];

int main()
{
  if(MyNodeId()) return 0;
    int n, m;
    scanf("%d %d %s %s", &n, &m, s1 + 1, s2 + 1);
    for(int i = 1; i <= m; i++)
	v[0][i] = make_pair(i, 0);
    bool i = false;
    for(int k = 1; k <= n; k++)
    {
	i = !i;
	v[i][0] = make_pair(k, 0);
	for(int j = 1; j <= m; j++)
	{
	    v[i][j] = min(v[!i][j], v[i][j-1]);
	    v[i][j].first++;
	    if(s1[k] == s2[j]) v[i][j] = min(v[i][j], v[!i][j-1]);
	    else v[i][j] = min(v[i][j], make_pair(v[!i][j-1].first + 1, v[!i][j-1].second + (s1[k] < s2[j])));
	}
    }
    printf("%d %d\n", v[i][m].first, v[i][m].second);
}