找相似串问题题解

偏执的太偏执、 2022-12-28 14:17 202阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入要求
     *  输出要求
 *  样例输入
 *  样例输出
 *  测试说明
 *  本题参考
 *  算法思路
 *   *  状态转移方程
 *  解题代码

--------------------

# 题目描述 #

找出最接近的相似串。

一般情况下，度量两个串 `S1` 和`S2` 的相似性，可以通过从一个串变换成另一个串所需要的最少操作次数来衡量，需要的操作次数越少，则越相似。

假设从一个串变化成另一个串所允许的操作只有两种：

**插入一个字符或者删除一个字符。无论是插 入还是删除一个符号，均算作一次操作。**

现给你一个串 `S` ，和一个串的集合 `T` ，让你找出集合 `T` 中与`S` 最相似的串。

## 输入要求 ##

> 输入的第一行为一个串 `S`  
> 第二行是一个整数 `n` ，范围 `0 < n < 20`，表示接下来集合 `T` 中的串的 个数。  
> 接下来 `n` 行，每行为一个串。  
> 注：所有字符串的长度不超过 50 。

## 输出要求 ##

> 请输出 T 中与 S 最相似的串，**如果有多个就输出多个串（按照输入时的顺序）**，每个串占一行。

# 样例输入 #

abcd
    4
    abd
    abdc
    abed
    aebcd

# 样例输出 #

abd
    aebcd

# 测试说明 #

对于第一个串`abd`，在`b`后插入一个`c`就可以变成`abcd`，操作次数为`1`次。

第二个串`abdc`，删除`d`后面的`c`，在`d`前面增加一个`c`，即可变成`abcd`，操作次数为`2`次。

第三个串`abed`，删除`d`前面的`e`，在`d`前面增加一个`c`，即可变成`abcd`，操作次数为`2`次。

第四个串`aebcd`，删除`a`后面的`e`即可变成`abcd`，操作次数为`1`次。

# 本题参考 #

[字符串相似度算法 递归与动态规划求解分析][Link 1]

# 算法思路 #

根据分析，用数组dp\[i\]\[j\]表示，以字符串a以i结尾，字符串b以j结尾时，他们从一个串转换到另一个串的操作数。

*  当`i = 0`时，可以得出，无论是在a串上添加，或者在b串上删除，都需要j次操作，即`dp[0][j] = j`;
 *  当`j = 0`时，可以得出，无论是在b串上添加，或者在a串上删除，都需要i次操作，即`dp[i][0] = i`;
 *  当`a[i] == b[j]`时，就看字符串a以i-1结尾，字符串b以j-1结尾时的最小操作数为多少，即`dp[i][j] = d[i-1][j-1]`;
 *  当`a[i] != b[j]`时，有两种操作，要么删除一个串的字符，要么添加一个串的字符，这两种操作都是对一个串进行的操作，所以`dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1`

## 状态转移方程 ##

![1][]

# 解题代码 #

#include <iostream>
    #include <string>
    using namespace std;
    
    string a;
    pair<int, string> s[100];
    int n;
    
    int fun(string a, string b)
    {
        
        int dp[100][100];
        
        for(int i = 0; i <= b.size(); i++)
            dp[0][i] = i;
        for(int i = 0; i <= a.size(); i++)
            dp[i][0] = i;
        
        for(int i = 1; i <= a.size(); i++){
        
            for(int j = 1; j <= b.size(); j++){
        
                if(a[i] == b[j])
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
            }
        }
        
        return dp[a.size()][b.size()];
    }
    
    int main()
    {
        
        cin >> a;
        cin >> n;
        for(int i = 0; i < n; i++){
        
            cin >> s[i].second;
            s[i].first = 0;
        }
        
        for(int i = 0; i < n; i++){
        
            s[i].first = fun(a, s[i].second);
            //cout << s[i].first << endl;
        }
        
        int min = 9999;
        for(int i = 0; i < n; i++)
            if(min >= s[i].first)
                min = s[i].first;
        
        for(int i = 0; i < n; i++){
        
            if(s[i].first == min)
                cout << s[i].second << endl;
        }
        
        return 0;
    }

[Link 1]: https://www.cnblogs.com/xudong-bupt/p/3182051.html
[1]: /images/20221120/bb720ea24c71400cba699b116a85adb7.png