题目描述

题目分析

使用dp思维，当前位置是否可行是有上一位置推来，计算出最大的可行位置即可

#include <stdio.h>
#include <string.h>#define N 256
int f(const char* s1, const char* s2)
{int a[N][N];int len1 = strlen(s1);int len2 = strlen(s2);int i,j;memset(a,0,sizeof(int)*N*N);int max = 0;for(i=1; i<=len1; i++){for(j=1; j<=len2; j++){if(s1[i-1]==s2[j-1]) {a[i][j] = a[i - 1][j - 1] + 1; if(a[i][j] > max) max = a[i][j];}}}return max;
}int main()
{printf("%d\n", f("abcdkkk", "baabcdadabc"));printf("%d\n", f("aaakkkabababa", "baabababcdadabc"));printf("%d\n", f("abccbaacbcca", "ccccbbbbbaaaa"));    printf("%d\n", f("abcd", "xyz"));printf("%d\n", f("ab", "ab"));return 0;
}