题目分析

题意

我们需要找出所有登录名对，这些登录名对之间的$"编辑距离"$不超过给定的阈值$d$。这里的编辑距离包括四种操作：

1.删除字符 2. 插入字符 3. 替换字符 4. 交换相邻字符

输入输出要求

• 输入：多组数据，每组包含$n$个登录名和距离阈值$d$
• 输出：所有满足距离$≤d$的登录名对，按字典序排序，并输出总对数

解题思路

关键点

1. 编辑距离计算：需要实现一个能够处理四种操作的编辑距离算法
2. 高效比较：对于$n≤200$，$O(n²)$的算法是可行的
3. 排序输出：需要按字典序输出结果

算法选择

使用动态规划计算扩展的编辑距离，处理四种操作：

• 标准编辑距离（插入、删除、替换）
• 额外处理相邻交换的情况

代码分析

数据结构

struct cstr {
    char s[22];
    bool operator <(const cstr& c)const {
        return strcmp(s,c.s)<0;
    }
}st[205];

存储登录名，并重载<运算符用于排序

核心函数

int dp(char *s1, char *s2) {
    int l1 = strlen(s1), l2 = strlen(s2);
    memset(d, 0, sizeof d);
    // 初始化边界条件
    for(int i=1; i<=l2; i++) d[0][i] = i;  // 全插入
    for(int i=1; i<=l1; i++) d[i][0] = i;  // 全删除
    
    for(int i=1; i<=l1; i++) {
        for(int j=1; j<=l2; j++) {
            d[i][j] = INF;
            // 标准编辑距离操作
            if(s1[i-1] == s2[j-1]) {
                d[i][j] = d[i-1][j-1];  // 字符相同
            } else {
                // 取插入、删除、替换的最小值
                d[i][j] = min(d[i][j-1], min(d[i-1][j], d[i-1][j-1])) + 1;
            }
            // 处理交换操作
            if(i>=2 && j>=2 && s1[i-2]==s2[j-1] && s1[i-1]==s2[j-2]) {
                d[i][j] = min(d[i][j], d[i-2][j-2]+1);  // 交换相邻字符
            }
            // 处理更复杂的交换情况
            if(i>=2 && j>=3 && s1[i-2]==s2[j-1] && s1[i-1]==s2[j-3]) {
                d[i][j] = min(d[i][j], d[i-2][j-3]+2);
            }
            if(i>=3 && j>=2 && s1[i-1]==s2[j-2] && s1[i-3]==s2[j-1]) {
                d[i][j] = min(d[i][j], d[i-3][j-2]+2);
            }
        }
    }
    return d[l1][l2];
}

主流程

1.读取输入并排序 2.双重循环比较所有登录名对 3. 输出符合条件的对

复杂度分析

• 时间复杂度：$O(n^2 * L^2)$，其中$L$是字符串最大长度（$16$）
• 空间复杂度：$O(nL)$

示例解析

对于输入：

8
2
omura
toshio
raku
tanaka
imura
yoshoi
hayashi
miura

程序会： 1.排序所有登录名 2. 计算每对之间的距离 3. 输出距离$≤2$的对

边界情况

• 空字符串
• 完全相同的字符串（距离$0$）
• 最大长度字符串（$15$字符）
• $d=0$时只输出完全相同的对

总结

这个解决方案通过动态规划高效计算了扩展的编辑距离，并正确处理了所有操作。排序和双重循环确保了结果的正确性和有序性。

标程

#include <cstdio>
#include <string.h>
#include <algorithm>
#define INF 0x3fffffff
using namespace std;
struct cstr{
    char s[22];
    bool operator <(const cstr& c)const{
        return strcmp(s,c.s)<0;
    }
}st[205];
int n,dis,d[20][20];
int dp(char *s1,char *s2){
    int l1=strlen(s1),l2=strlen(s2);
    memset(d,0,sizeof d);
    for(int i=1;i<=l2;i++)d[0][i]=i;
    for(int i=1;i<=l1;i++)d[i][0]=i;
    for(int i=1;i<=l1;i++){
        for(int j=1;j<=l2;j++){
            d[i][j]=INF;
            if(s1[i-1]==s2[j-1]){
                d[i][j]=d[i-1][j-1];
            }else{
                d[i][j]=min(d[i][j-1],min(d[i-1][j],d[i-1][j-1]))+1;
            }
            if(i>=2&&j>=2&&s1[i-2]==s2[j-1]&&s1[i-1]==s2[j-2]){
                d[i][j]=min(d[i][j],d[i-2][j-2]+1);
            }
            if(i>=2&&j>=3&&s1[i-2]==s2[j-1]&&s1[i-1]==s2[j-3]){
                d[i][j]=min(d[i][j],d[i-2][j-3]+2);
            }
            if(i>=3&&j>=2&&s1[i-1]==s2[j-2]&&s1[i-3]==s2[j-1]){
                d[i][j]=min(d[i][j],d[i-3][j-2]+2);
            }
        }
    }
    return d[l1][l2];
}

int main(){
   // freopen("test.in","r",stdin);
    while(scanf("%d",&n),n){
        scanf("%d",&dis);
        for(int i=0;i<n;i++)scanf("%s",st[i].s);
        sort(st,st+n);
        int tot=0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                int x=dp(st[i].s,st[j].s);
                if(x<=dis){
                    tot++;
                    printf("%s,%s\n",st[i].s,st[j].s);
                }
            }
        }
        printf("%d\n",tot);
    }
    return 0;
}