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
124
125
#include <iostream>
#include <string>
#include <algorithm>
#include "message.h"

using namespace std;

int n, m;
string a, b;

int lZmian1[100002], lZmian2[100002], lSzokow1[100002], lSzokow2[100002];//[n][m]
int *lZmianTer=lZmian1, *lZmianPoprz=lZmian2, *lSzokowTer=lSzokow1, *lSzokowPoprz=lSzokow2;

void licz(int doIlu)
{
  for (int j=0; j<=m; ++j)
    lZmianTer[j]=j;
  for (int i=1; i<=doIlu; ++i)
  {
    if ((i&1023)==0) 
      cerr<<i<<endl;
      
    swap(lZmianTer, lZmianPoprz);
    swap(lSzokowTer, lSzokowPoprz);
    lZmianTer[0]=i;
    for (int j=1; j<=m; ++j)
    {
      int ll=lZmianPoprz[j-1]+(a[i-1]==b[j-1] ? 0 : 1);
      int lz=min(lZmianTer[j-1]+1, min(lZmianPoprz[j]+1, ll));
      lZmianTer[j]=lz;
      int lsz=1000000;
      if (lz==lZmianTer[j-1]+1)
        lsz=lSzokowTer[j-1];
      if (lz==lZmianPoprz[j]+1)
        lsz=min(lsz, lSzokowPoprz[j]);
      if (lz==ll)
        lsz=min(lsz, lSzokowPoprz[j-1]+(a[i-1]<b[j-1] ? 1 : 0));
      lSzokowTer[j]=lsz;
    }    
  }
} 

int qlZmian1[100002], qlZmian2[100002], qlSzokow1[100002], qlSzokow2[100002];//[n][m]
int *qlZmianTer=qlZmian1, *qlZmianPoprz=qlZmian2, *qlSzokowTer=qlSzokow1, *qlSzokowPoprz=qlSzokow2;

void qlicz(int doIlu)
{
  for (int j=0; j<=m; ++j)
    qlZmianTer[j]=j;
  for (int i=1; i<=doIlu; ++i)
  {
    if ((i&1023)==0) 
      cerr<<i<<endl;
      
    swap(qlZmianTer, qlZmianPoprz);
    swap(qlSzokowTer, qlSzokowPoprz);
    qlZmianTer[0]=i;
    for (int j=1; j<=m; ++j)
    {
      int ll=qlZmianPoprz[j-1]+(a[i-1]==b[j-1] ? 0 : 1);
      int lz=min(qlZmianTer[j-1]+1, min(qlZmianPoprz[j]+1, ll));
      qlZmianTer[j]=lz;
      int lsz=1000000;
      if (lz==qlZmianTer[j-1]+1)
        lsz=qlSzokowTer[j-1];
      if (lz==qlZmianPoprz[j]+1)
        lsz=min(lsz, qlSzokowPoprz[j]);
      if (lz==ll)
        lsz=min(lsz, qlSzokowPoprz[j-1]+(a[i-1]<b[j-1] ? 1 : 0));
      qlSzokowTer[j]=lsz;
    }    
  }
}

int main()
{
  if (MyNodeId()>1)
    return 0;
  ios_base::sync_with_stdio(false);
  cin>>n>>m>>a>>b;
  if (n*(long long)m<=10000000 || NumberOfNodes()==1)
  {
    if (MyNodeId())
      return 0;
    licz(n);
    cout<<lZmianTer[m]<<' '<<lSzokowTer[m]<<endl;
    return 0;
  }
  
  int srodek=(n+16)/2;
  if (MyNodeId())
  {
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    qlicz(n-srodek);
    for (int j=0; j<=m; ++j)
    {
      PutInt(0, qlZmianTer[j]);
      PutInt(0, qlSzokowTer[j]);
    }
    Send(0);
    return 0;
  }
  licz(srodek);
  Receive(1);
  for (int j=0; j<=m; ++j)
  {
    qlZmianTer[j]=GetInt(1);
    qlSzokowTer[j]=GetInt(1);
  }
  
  int najL=1000000, najSz=1000000;
  for (int j=0; j<=m; ++j)
  {
    int l=lZmianTer[j]+qlZmianTer[m-j], s=lSzokowTer[j]+qlSzokowTer[m-j];
    if (l<najL || (l==najL && s<najSz))
    {
      najL=l;
      najSz=s;
    }
  }
  cout<<najL<<' '<<najSz<<endl;
  
  return 0;
}