source: app/src/cor/corr.cc @ ff0fc99

//---------------------------------------------------------------------------

#include "corr.hh"

#define MAXPATH 256

#define min(x,y) ((x<y)?(x):(y))
#define max(x,y) ((x>y)?(x):(y))


int Corr::ed(int i,int j)
{
  if(i==-1)
    return j+1;
  if(j==-1)
    return i+1;
  if(i==-2 || j==-2)
    return n+1;

  if(X[i]==Y[j])
    return H2[i-1][j-1];
  if(X[i-1]==Y[j] && X[i]==Y[j-1])
    return 1+min(H2[i-2][j-2],min(H2[i][j-1],H2[i-1][j]));
  return 1+min(H2[i-1][j-1],min(H2[i][j-1],H2[i-1][j]));

/*
  if(X[i]==Y[j])
    return H[(i-1)+2][(j-1)+2];
  if(X[i-1]==Y[j] && X[i]==Y[j-1])
    return 1+min(H[(i-2)+2][(j-2)+2],min(H[(i)+2][(j-1)+2],H[(i-1)+2][(j)+2]));
  return 1+min(H[(i-1)+2][(j-1)+2],min(H[(i)+2][(j-1)+2],H[(i-1)+2][(j)+2]));
*/
}

int Corr::cuted(int j)
{
  int l=max(0,j-t);
  int u=min(m,j+t);
  int ce=j+t;
  for(int k=l;k<=u;k++)
  {
    if(H2[k][j]<ce)//if(H[(k)+2][(j)+2]<ce)
      ce=H2[k][j];//ce=H[(k)+2][(j)+2];
  }
  return ce;
}

/*
void Corr::recomputeH(int j)
{
  for(int i=0;i<=m;i++)
    H[(i)+2][(j)+2]=ed(i,j);
}
*/

void Corr::recomputeH(int j)
{
  int lo=max(0,j-t-2);
  int hi=min(m,j+t+2);
  for(int i=lo;i<=hi;++i)
    H2[i][j]=ed(i,j);//H[(i)+2][(j)+2]=ed(i,j);
}


int Corr::correct(const char* w, Words& tab)
{
  long int path[MAXPATH]={0};
  int i;                                    // row index (X)
  int j;                                    // column index (Y)
  long state=0;

  strcpy(X,w);
  m=strlen(X)-1;
  n=m+t;

  for(i=(-2);i<=m;i++)
    H[(i)+2][(-2)+2]=n;
  for(i=(-1);i<=m;i++)
    H[(i)+2][(-1)+2]=(i)+1;
  for(j=(-2);j<=n;j++)
    H[(-2)+2][(j)+2]=n;
  for(j=(-1);j<=n;j++)
    H[(-1)+2][(j)+2]=(j)+1;

  for(j=0; j<=n; ++j)
    for(i=0; i<=m; ++i)
      H[i+2][j+2]=t+1;

  int more=1;
  bool cont=false;

  strcpy(Y,"");
  j=0;
  state=0;
  int count=0;
  while(more)
  {
    if(!empty(state))
    {
      Y[j]=input(state);
      recomputeH(j);
      if(cuted(j)<=t)
      {
        int edd;
        if(final(next(state)) && (edd=H[(m)+2][(j)+2])<=t)
        {
          char* out=new char[j+2];
          strncpy(out,Y,j+1);
          out[j+1]='\0';
          //          if(cont) putchar(' ');
          cont=true;
          //          printf("%i,%s", edd,out);
          //          cout << out << "(" << edd << ")" << endl;
          tab.add(out);
          count++;
        }
        path[j++]=state;
        state=next(state);
        continue;
      }
      else
        if(continued(state))
        {
          state++;
          continue;
        }
    }
    //backtracking
    do
      if(j>0)
        j--;
      else
        more=0;
    while(more && !continued(path[j]));
    state=path[j]+1;
  }
  return count;
}


//---------------------------------------------------------------------------