uva10405 - Longest Common Subs（最长公共子序列）

本文主要是介绍uva10405 - Longest Common Subs（最长公共子序列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

对于这个题我们写代码的时候要注意两点

1、后台测试字符串中含有空格

2、初始化如果不需要的话，就注释掉。

我的就是因为不必要的初始化，使得代码跑了52ms，注释掉后跑了16ms

代码如下：

#include <cstdio>
#include <cstring>
#define max(s,t) s>t?s:t
char a[1010], b[1010];
int f[1010][1010];
int solve()
{//memset(f,0,sizeof(f));int lena = strlen(a), lenb = strlen(b), tt, tt1, tt2;for(int i = 0; i < lena; i++){for(int j = 0; j < lenb; j++){if(a[i]==b[j]){tt = i==0||j==0?0:f[i-1][j-1];f[i][j] = tt+1;}else{tt1 = i==0? 0 : f[i-1][j];tt2 = j==0? 0 : f[i][j-1];f[i][j] = max(tt1,tt2);}}}return f[lena-1][lenb-1];
}
int main ()
{while(gets(a)){gets(b);printf("%d\n",solve());}return 0;
}

这篇关于uva10405 - Longest Common Subs（最长公共子序列）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---