题目大意：给出两个字符串，求两个字符串的最长公共字串。
思路：慢慢重心开始有贪心转向动态规划了，这题就是简单的动态规划题。以题目的第一组测试数据为例。abcfbc
abfcab。
从图中明显可以看出：
F[i][j]=F[i-1][j-1]+1；（a[i]==b[j]）
F[i][j]=max(F[i-1][j],F[i][j-1])(a[i]!=b[j]);
n由于F(i,j)只和F(i-1,j-1), F(i-1,j)和F(i,j-1)有关, 而在计算F(i,j)时, 只要选择一个合适的顺序, 就可以保证这三项都已经计算出来了, 这样就可以计算出F(i,j). 这样一直推到f(len(a),len(b))就得到所要求的解了.
#include<stdio.h> #include<string.h> #define maxn 1000+10 char a[maxn],b[maxn]; int f[maxn][maxn]; int max(int x,int y) { return x>y?x:y; } int main() { while(~scanf("%s %s",a,b)) { int len1,len2,i,j; len1=strlen(a); len2=strlen(b); memset(f,0,sizeof(f));//初始化个位置为零 for(i=1;i<=len1;i++) for(j=1;j<=len2;j++) { if(a[i-1]==b[j-1]) f[i][j]=max(f[i-1][j-1],f[i-1][j-1]+1); else f[i][j]=f[i-1][j]>f[i][j-1]?f[i-1][j]:f[i][j-1]; } printf("%d\n",f[len1][len2]); } }
