#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 **********/
}
![avatar](https://profile-avatar.csdnimg.cn/default.jpg!1)
摸鱼dba
- 粉丝: 0
- 资源: 40
最新资源
- python-leetcode题解之117-Populating-Next-Right-Pointers
- python-leetcode题解116-Populating-Next-Right-Pointers-in-Each-Node
- python-leetcode题解之115-Distinct-Subsequences
- python-leetcode题解之114-Flatten-Binary-Tree-to-Linked-List
- python-leetcode题解之113-Path-Sum-II
- python-leetcode题解之112-Path-Sum
- python-leetcode题解之111-Minimum-Depth-of-Binary-Tree
- python-leetcode题解之110-Balanced-Binary-Tree
- python-leetcode-109-Convert-Sorted-List-to-Binary-Search-Tree
- python-leetcode题解之108-Convert-Sorted-Array-to-Binary-Search-Tree
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![feedback](https://img-home.csdnimg.cn/images/20220527035711.png)
![feedback](https://img-home.csdnimg.cn/images/20220527035711.png)
![feedback-tip](https://img-home.csdnimg.cn/images/20220527035111.png)