// myclass13.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <math.h>
#include <stdio.h>
using namespace std;

float sim_string(string a,string b)
{
	int k=0,i,j;
	float partone,parttwo=0.0,sim,v;
	int m=a.length(),n=b.length();
	int *check_b=new int[n];
	for(j=0;j<n;j++)
		check_b[j]=0;

	int **d=new int*[m];
	  for(i=0;i<m;i++)
	  d[i]=new int[n];  

	  for(i=0;i<m;i++)
		  for(j=0;j<n;j++)
			  d[i][j]=0;
	
	for(i=0;i<m;i++)
	{
		for(j=0;j<n;j++)
		{
			if(a[i]==b[j]&&check_b[j]==0)
			{
				k++,check_b[j]=1,d[i][j]=1;
			}
		}

	}

	/*for(j=0;j<n;j++)
		cout<<check_b[j]<<endl;*/

//cout<<m<<endl<<n<<endl<<k<<endl;
	partone=(float)k/(m+n-k);
	
	v=float(1)/k;

	for(i=0;i<m;i++)
	{
		for(j=0;j<n;j++)
			if(d[i][j]==1)
			{
				float temp=(float)1/(1+abs(j-i));
					parttwo+=v*temp;
			}
	}

	sim=0.6*partone+0.4*parttwo;
	
	return sim;

	delete[] check_b;
	for(i=0;i<=m;i++)
			  delete[] d[i];
		 delete[] d;

}

float longest_common_subsequence(string a,string b)
{
	int count,i,j,flag;
  
	//---------------獲取兩個要評估的字符串的長度--------------------------
	int m=a.length(),n=b.length(); 
	 /* cout<<m<<endl<<n<<endl;*/
	//----------------為存儲中間結果的二維數組分配空間---------------
	  int **d=new int*[m+1];
	  for(int k=0;k<m+1;k++)
	  d[k]=new int[n+1];  

	  /*for(i=0;i<=m;i++)
		  for(j=0;j<=n;j++)
			  d[i][j]=1;
		  for(i=0;i<=m;i++)
		  for(j=0;j<=n;j++)
			  cout<<d[i][j]<<endl;*/


	  //-----------Clear the dynamic programming table-------------------------------
	  d[0][0]=0;
	  for(i=1;i<=m;d[i][0]=0,i++)
		  ;
	  for(j=1;j<=n;d[0][j]=0,j++)
		  ;

		  //---------------dynamic programming--------------------------
		  for(i=1;i<=m;i++)                     //for each pair of
		  {
			  for(j=1;j<=n;j++)                 //chars in string
			  {
				  if(a[i-1]==b[j-1])			//are they equal?
					  d[i][j]=d[i-1][j-1]+1;	// one more
				  else 
				  {  
					  if(d[i][j-1]>=d[i-1][j])  //or pick
					  d[i][j]=d[i][j-1];		//a smaller 
				  else d[i][j]=d[i-1][j-1];	   //neighbor
				  }
			  }
		  }
			/*	for(i=0;i<=m;i++)
		  for(j=0;j<=n;j++)
		   cout<<d[2][2]<<endl;
			  cout<<d[2][3]<<endl;*/

		//----------------display the subsequence----------------------
				  flag=count=d[m][n];
				  char *result=new char[count+1];
				  result[count]='\0';
				  for(i=m,j=n;(i!=0)&&(j!=0);)
				  {
					  if(d[i][j]==d[i-1][j])
						  i--;
					  else if(d[i][j]==d[i][j-1])
						  j--;
					  else {
						  result[--count]=a[i-1];
						  i--,j--;
					  }
				  }
			/*for(i=0;i<flag;i++)
				cout<<result[i];
			cout<<endl;*/
			
            
	  //-----------釋放內存------------
          //delete result;
		float longest_sim=float(flag)/(m+n-flag);
		return longest_sim;
		  
			for(i=0;i<=m;i++)
			  delete[] d[i];
		 delete[] d;
		 
		delete [] result;
}


int main(int argc, char* argv[])
{
string a="cd",b="dc";
cout<<sim_string(a,b)<<endl<<longest_common_subsequence(a,b)<<endl;
float sim=0.7*sim_string(a,b)+0.3*longest_common_subsequence(a,b);
cout<<sim<<endl;
	return 0;
}