题目描述
小乐乐有字符串str1,str2。
小乐乐想要给他们找朋友。
小乐乐想知道在这两个字符串中最多能匹配出多长的相同子串(可非连续)。
输入描述:
第一行输入字符串str1;
第二行输入字符串str2;
数据保证字符串长度小于1000,且非空,字符串仅由小写字母组成。
|
输出描述:
示例1
输入
输出
思路:
动态规划入门题,两层 for循环分别遍历两个字符串的字符,若s1【i】 == s2【j】,则dp【i】【j】= dp【i - 1】【j - 1】+ 1,否则dp【i】【j】= max(dp【i - 1】【j】,dp【i】【j - 1】)即可
代码:
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; char s1[1005], s2[1005]; int dp[1005][1005]; int main () { memset(dp, 0, sizeof(dp)); scanf("%s", s1 + 1); scanf("%s", s2 + 1); int n1 = strlen(s1 + 1); int n2 = strlen(s2 + 1); for (int i = 1; i <= n1; i++) { for (int j = 1; j<= n2; j++) { if(s1[i] != s2[j]) { dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]); } else { dp[i][j] = dp[i - 1][j - 1] + 1; } } } printf("%dn", dp[n1][n2]); return 0; }
|
近期评论