最长公共字符串.cpp

这里面是很多经典算法的源代码

#include<stdio.h>
#include<string.h>
char a[200],b[200],c[200];
int dp[200][200];
int bigger(int a1,int b1 )
{
	return a1>b1?a1:b1;
}
main()
{
	int m,n,k,i,j;
	int getlength(int ,int );
	void getch(int,int ,int);
	scanf("%s%s",a,b);
	m=strlen(a);
	n=strlen(b);
	for(i=0;i<=m;i++)
		for(j=0;j<=n;j++)//<=n,m
		{
			dp[i][j]=-1;
		}
	k=getlength(m,n);
	printf("%d",k);
	c[k]='\0';
	getch(m,n,k);
	printf("\n%s",c);
}
int getlength(int i,int j)
{
	if(dp[i][j]!=-1)
	{
		return dp[i][j];
	}
	if(i==0||j==0)
	{
		dp[i][j]=0;
		return dp[i][j];
	}
	if(a[i-1]==b[j-1])
	{
		dp[i][j]=getlength(i-1,j-1)+1;
		return dp[i][j];
	}
	else if(a[i-1]!=b[j-1])
	{
		dp[i][j]=bigger(getlength(i-1,j),getlength(i,j-1));
		return dp[i][j];
	}
}
 void getch(int i,int j,int k)
{
	if(i==0||j==0)
	{
		return ;
	}
	 if(dp[i-1][j]==dp[i][j])//不用再调用getlength了
	{
		getch(i-1,j,k);
	}
	else if(dp[i][j-1]==dp[i][j])
	{
		getch(i,j-1,k);	
	}
	else 
	{
		c[k-1]=a[i-1];
		getch(i-1,j-1,k-1);
	}
}