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
#include "message.h"
#include <iostream>
#include <cstdio>
#include <ctime>
#include <set>
#include <vector>
#include <algorithm>
#define LL long long
#define ff first
#define ss second
#define PB push_back
#define MP make_pair
#define DEBUG(x) cerr<<#x<<" "<<(x)<<endl;
using namespace std;
const int MAXN = 100005;
pair<int, int> tab[MAXN];
pair<int, int>dp[MAXN];
pair<int, int>pref[MAXN];
int n, m;
char s[MAXN], w[MAXN];
int main()
{
  scanf("%d %d", &n, &m);
  scanf("%s", &s[1]);
  scanf("%s", &w[1]);
  int N = NumberOfNodes();
  int ID = MyNodeId();
  int poczatek = ID*n/N+1;
  int koniec = (ID+1)*n/N;
  int K = -poczatek+1;
  for(int i=poczatek-1; i<=koniec; i++)
    pref[i+K] = MP(i, 0);
    for(int i=1; i<=m; i++)
    {
     
      if(ID > 0 && i%100 == 1)
      {
	Receive(ID-1);
	for(int j=i; j<=min(m, i+99); j++)
	{
	  tab[j].ff = GetInt(ID-1);
	  tab[j].ss = GetInt(ID-1);
	}
      }
      dp[0] = tab[i];
      if(ID == 0)
	dp[0] = MP(i, 0);
      for(int j=poczatek; j<=koniec; j++)
      {
	int P = j+K;
	if(w[i] == s[j])
	  dp[P] = pref[P-1];
	else
	{
	  pair<int, int> x = min(dp[P-1], pref[P]);
	  if(x > pref[P-1])
	  {
	    if(w[i] > s[j])
	    {
	      dp[P] = MP(pref[P-1].ff+1, pref[P-1].ss+1);	      
	    }
	    else
	    {
	      dp[P] = MP(pref[P-1].ff+1, pref[P-1].ss);
	    }
	  }
	  else
	  {
	    dp[P] = MP(x.ff+1, x.ss);
	  }
	}
      }
      if(ID < N-1)
      {
	PutInt(ID+1, dp[koniec+K].ff);
	PutInt(ID+1, dp[koniec+K].ss);
      }
      if((i==m || i%100==0) && ID < N-1)
      	Send(ID+1);
      for(int j=poczatek-1; j<=koniec; j++)
      {
// 	cout<<i<<" "<<j<<" "<<dp[j+K].ff<<" "<<dp[j+K].ss<<endl;
	pref[j+K] = dp[j+K];
      }
    }
    if(ID == N-1)
      printf("%d %d", dp[koniec+K].ff, dp[koniec+K].ss);
  
}