ACM俱乐部密码

#include <stdio.h>        //不用动态规划的话运行960ms时间感人，用动态规划就变成1ms
#include <string.h>       //用动态规划时需主要要保存三个状态来比较，分别是最大值，字符串1的当前位置，字符串2的当前位置
char str1[101],str2[101];   //当最大值！=-1且等于字符串1当前位置且等于字符串2当前位置时才返回动规数组
int count1[100];
char count2[101];
char count3[101];
int found(char *cheak,int i)
{
	int o,count=0,max=0;

	if (count1[i]!=-1&&count2[i]==str1[i]&&count3[i]==*cheak)
		return count1[i];
	for (o=i;str1[o];o++)
	{
		if (strchr(cheak,str1[o]))
			count=found(strchr(cheak,str1[o])+1,o+1)+1;
		if (max<count)
			max=count;
	}
	count3[i]=*cheak;
	count2[i]=str1[i];
	count1[i]=max;
	return count1[i];			
}

int main()
{
	memset(count1,-1,sizeof(int)*100);
	memset(count2,'\0',101);
	memset(count3,'\0',101);
	while (gets(str1))
	{
		char *cheak;
		gets(str2);
		cheak=str2;
		printf("%d\n",found(cheak,0));
	}
	return 0;
}

描述

ACM俱乐部的墙上写着两行密码字符串，据说能破解其中奥秘的人计算机考研一定过。
如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，则字符串一称之为字符串二的子串。注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。
现在求ACM俱乐部两行密码字符串的最长公共子串的长度。

输入

每组测试数据输入两行，每行输入一个字符串（长度<=100）。

输出

每组测试数据输出一行，输出ACM俱乐部两行密码字符串的最长公共子串的长度。

样例输入1

BDCABA
ABCBDAB
JXVTEWSNHACJDE
LDAAJNOPPERLJBPUUNHWSYYODMGW

样例输出1

4
5