对于这类题型，基本上都是用动态规划来解决。我们可以用两个for循环进行查找，然后用一个数组来记录相同字符的数量。
#include<stdio.h> #include<string.h> char a[1005]; char b[1005]; int dp[1005][1005]; int max(int a,int b){ return a>b?a:b; } int main(){ int T; int lena,lenb; scanf("%d",&T); while(T--){ scanf("%s",a); scanf("%s",b); lena=strlen(a); lenb=strlen(b); memset(dp,0,sizeof(dp)); for(int i=1;i<=lena;i++){ for(int j=1;j<=lenb;j++){ if(a[i-1]==b[j-1])dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);//比较第一层for循环前一个和当前的相同字符数量 } } printf("%d\n",dp[lena][lenb]); } }优化后的代码：
#include <stdio.h> #include <string.h> char a[1001], b[1001]; int dp[1001], t, old, tmp; int main(){ scanf("%d", &t); getchar(); while(t--){ gets(a); gets(b); memset(dp, 0, sizeof(dp)); int lena=strlen(a), lenb=strlen(b); for(int i=0; i<lena; i++){ old=0; for(int j=0; j<lenb; j++){ tmp = dp[j]; if(a[i]==b[j]) dp[j] = old+1; else if(dp[j-1]>dp[j])dp[j]=dp[j-1]; old = tmp; //此处我们用old代替了dp[i-1][j-1] } } printf("%d\n", dp[lenb-1]); } return 0; }