编辑代码

#include <iostream>
#include <string.h>
#define MAXLEN 100
using namespace std;
void lcslength(char x[], char y[], int m, int n, int c[][MAXLEN], int b[][MAXLEN])
{
	int i, j;
	for (i = 0; i <= m; i++)
		c[i][0] = 0;
	for (j = 1; j <= n; j++)
		c[0][j] = 0;
	for (i = 1; i <= m; i++)
	{
		for (j = 1; j <= n; j++)
		{
			if (x[i - 1] == y[j - 1])
			{
				c[i][j] = c[i - 1][j - 1] + 1;
				b[i][j] = 0;
			}
			else if (c[i - 1][j] >= c[i][j - 1])
			{
				c[i][j] = c[i - 1][j];
				b[i][j] = 1;
			}
			else
			{
				c[i][j] = c[i][j - 1];
				b[i][j] = -1;
			}
		}
	}
}
 
void printlcs(int b[][MAXLEN], char *x, int i, int j)
{
	if (i == 0 || j == 0)
		return;
	if (b[i][j] == 0)
	{
		printlcs(b, x, i - 1, j - 1);
		printf("%c ", x[i - 1]);
	}
	else if (b[i][j] == 1)
		printlcs(b, x, i - 1, j);
	else
		printlcs(b, x, i, j - 1);
}
 
void longestcommonsubstring(char x[], char y[], int m, int n, int c[][MAXLEN]) 
{
	int i, j;
	int k, xpos, max;
	max = -1;
 	for (i = 0; i <= m; i++)
		c[i][0] = 0; 
	for (j = 1; j <= n; j++)
		c[0][j] = 0; 
	for (i = 1; i <= m; i++)
	{
		for (j = 1; j <= n; j++)
		{
			if (x[i - 1] == y[j - 1])
				c[i][j] = c[i - 1][j - 1] + 1;
			else
				c[i][j] = 0;
			if (c[i][j] > max) {
				max = c[i][j];
				xpos = i;
			}
		}
	}
	char lcs[MAXLEN] = {};
	for (i = xpos - 1, k = max - 1; k >= 0; k--, i--)
		lcs[k] = x[i];
	printf("%s\n", lcs);
}
 
 
int main(int argc, char **argv)
{
	char x[MAXLEN] = { "FOSHSTS" };
	char y[MAXLEN] = { "FOSSTSS" };
	int b[MAXLEN][MAXLEN] = {};
	int c[MAXLEN][MAXLEN] = {};
	int d[MAXLEN][MAXLEN] = {};
	int m, n;
 
	m = strlen(x);
	n = strlen(y);
 
	printf("最长公共子序列为: ");
	lcslength(x, y, m, n, c, b);
	printlcs(b, x, m, n);
	printf("\n");
 
	printf("最长公共字串为：: ");
	longestcommonsubstring(x, y, m, n, d);
	printf("\n");
	return 0;
}