stringcmp.cpp

来自「设A和B是长度相同的2个字符串。A和B的距离定义为相应位置字符距离之和。2个非空」· C++ 代码 · 共 137 行

#include <iostream>
#include <string>
#include <fstream>
#include <math.h>

using namespace std;

long k;

unsigned long MinDistance(const string & A,const string & B)
{
	unsigned long m,n;
	
	long t;
	
	m=A.length();
	n=B.length();

	long * a=new long[n+1];    //下标 0..n
	long * b=new long[n+1];

	int i,j,p,q;
	p=0;
	q=0;
    for (i=0;i<=m;++i)
	{
		for (j=0;j<=n;++j)
		{
			if (i==0)    //第0行
			{
				if (j==0) a[0]=0;   //0,0
				else
				{   
					a[j]=j*k;
                    if (B[j-1]==' ') a[j]-=(++p)*k;
				}
			}
			else //i>0
			{
				if (j==0)  //第0列
				{
					b[0]=i*k;
					if (A[i-1]==' ') b[j]-=(++q)*k;
				}
				
				else
				{
					
					t=A[i-1]-B[j-1];

					if (t<0) t=-t;

					if (t!=0)
						if ((A[i-1]==' ') || (B[j-1]==' ')) t=k;
						
						b[j]=a[j-1]+t;

						t=a[j];

						if (A[i-1]!=' ') 
						{
							t=t+k;
						}
						

						if (t<b[j])
						{
							b[j]=t;
						}
						

						t=b[j-1];

						if (B[j-1]!=' ') 
						{
							t=t+k;
						}
						
							if (t<b[j])
						{
							b[j]=t;
						}
						
				}
			}
		
			
		}
	    
		//后一行覆盖前一行
		if (i>0) memcpy(a,b,(n+1)*sizeof(long));
		
		
	}

    unsigned long result=b[n];

	delete [] b;
	delete [] a;
	

	return result;
}
void main()
{
	string A,B;

	ifstream fin("input.txt");
   
	
    if (fin.fail()!=0) 
	{
	  cout<<"Open Input File Fail!";
	  return;
	}

    //从input.txt中获取输入数据
	getline(fin,A);
    getline(fin,B);

	fin>>k;

	long result=MinDistance(A,B);
	
    ofstream fout("output.txt");
    if (fout.fail()!=0) 
	{
	  cout<<"Open Output File Fail!";
	  return;
	}

	fout<<result<<endl;

    
}