头歌之第四章 动态规划（作业2-必做）.rar

#include <iostream> #include <cstring> using namespace std; const int MAX=60; void Similar() { /********** Begin **********/ char s[MAX]; int n,end; cin >> s>>n;//读取主串和子串个数 int len_s = strlen(s); char arr[20][MAX]; int caozuo[20];//存操作次数 int dp[MAX][MAX];//用数组dp[i][j]表示，子串从1-i转换到主串的操作数。 for (int i = 0; i < n; i++)//读取子串 { cin>>arr[i]; } for (int i = 0; i < len_s; i++) { dp[0][i] = i; //处理边界 } for (int k = 0; k < n; k++)//第k个子串 { int len = strlen(arr[k]);//子串长度 //初始化 for (int j = 0; j < len; j++) dp[j][0] = j; for (int i = 1; i < len_s; i++)//i为主串下标 { for (int j = 1; j < len; j++)//j为子串下标 { if (s[i] == arr[k][j]) dp[i][j] = dp[i - 1][j - 1]; else dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1; } } caozuo[k] = dp[len_s-1][len-1];//存每个子串的最小操作数 } end = caozuo[0]; for (int i = 1; i < n; i++) end = min(end, caozuo[i]); //找到最小操作数 for (int i = 0; i < n; i++) { if (caozuo[i] == end) cout << arr[i] << endl; //输出对应串 } /********** End **********/ }