题意:给定串长<=100000的母串和n(n<=10)且长度<=10的小串,问哪一个小串在母串中通过增加删除修改一个字母的操作数(即编辑距离)最小变成
母串中的substring,求最小的编辑距离,和对应字典序最小的字串。
题解:比赛的时候看了一眼,substring看着有点晃,就搞别的了,还是自己太弱最后没有时间仔细想想这个题目。
对于两个串的编辑距离可以用O(n*m)的复杂度来搞,对于字串只需要做一点修改即可,具体见代码注释。
对于长度为len的串,要想成为母串的substring最大的编辑距离不超过len。
对于题目描述的问题,因为环的存在考虑把原串的前10位直接复制到原串后面,但是需要注意的是如果母串abcd,子串abcda,最少需要操作次数是1,
但是将abcd复制后变成abcdabcd,abcda成了子串,答案变成了0,所以如果当前串长l*2 >= 母串长,需要循环原串起始位置暴力即可。
Sure原创,转载请注明出处。
#include <iostream> #include <cstdio> #include <string.h> #define MIN(a , b) ((a) < (b) ? (a) : (b)) using namespace std; const int inf = 1 << 29; const int maxn = 100002; const int maxm = 12; char str[maxn],dtr[maxn + maxm],dic[maxm][maxm],huan[maxm]; int dp[maxn + maxm][maxm]; int m,len,llen; int CompareString(char *s1,char *s2,int l1,int l2) //dp[i][j]表示s2前j位作为s1串前i位的字串,且匹配的编辑距离 { memset(dp,0,sizeof(dp)); //for(int i=0;i<=l1;i++) 如果这四行加上,dp[i][j]表示的是s1串前i位与s2前j位的全部匹配的编辑距离 //{ // dp[i][0] = i; //} for(int i=0;i<=l2;i++) { dp[0][i] = i; } for(int i=1;i<=l1;i++) { for(int j=1;j<=l2;j++) { int cost = (s1[i-1] == s2[j-1]) ? 0 : 1; dp[i][j] = MIN(dp[i-1][j-1] + cost , MIN(dp[i-1][j] + 1 , dp[i][j-1] + 1)); } } int res = inf; for(int i=0;i<=l1;i++) { res = MIN(res , dp[i][l2]); } return res; } void solve() { len = strlen(str); strcpy(dtr , str); for(int i=0;i<maxm;i++) { dtr[i+len] = str[i]; } llen = len + maxm; dtr[llen] = '\0'; scanf("%d",&m); getchar(); int pos = -1,ans = inf; for(int i=0;i<m;i++) { scanf("%s",dic[i]); int l = strlen(dic[i]); if((l << 1) < len) { int tmp = CompareString(dtr , dic[i] , llen , l); if(tmp < ans || (tmp == ans && strcmp(dic[pos] , dic[i]) > 0)) { ans = tmp; pos = i; } } else { for(int s=0;s<len;s++) { for(int j=0;j<len;j++) { huan[j] = str[(s+j) % len]; } huan[len] = '\0'; int tmp = CompareString(huan , dic[i] , len , l); if(tmp < ans || (tmp == ans && strcmp(dic[pos] , dic[i]) > 0)) { ans = tmp; pos = i; } } } } printf("%s %d\n",dic[pos],ans); return; } int main() { while(~scanf("%s",str)) { solve(); } return 0; }