結果

問題 No.225 文字列変更(medium)
ユーザー 東前頭十一枚目
提出日時 2019-03-30 17:48:38
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 7 ms / 5,000 ms
コード長 1,352 bytes
コンパイル時間 1,792 ms
コンパイル使用メモリ 171,272 KB
実行使用メモリ 7,040 KB
最終ジャッジ日時 2024-11-15 20:44:51
合計ジャッジ時間 2,584 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const long long LINF=8931145141919364364,LMOD=998244353;
inline long long mod(long long n,long long m){return(n%m+m)%m;}
// const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};

struct LevenshteinDistance{
    const int costInsert,costErase,costReplace;
    LevenshteinDistance(int i,int e,int r):
        costInsert(i),costErase(e),costReplace(r)
        {}
    int distance(string& s1,string& s2){
        int n1=s1.size(),n2=s2.size();
        // dp[i][j]:=s1のi文字目までとs2のj文字目までの距離
        vector<vector<int>> dp(n1+1,vector<int>(n2+1,INF));
        for(int i=0;i<=max(n1,n2);i++){
            if(i<=n1) dp[i][0]=i;
            if(i<=n2) dp[0][i]=i;
        }
        for(int i=1;i<=n1;i++){
            for(int j=1;j<=n2;j++){
                dp[i][j]=min(dp[i][j],dp[i-1][j]+costInsert);
                dp[i][j]=min(dp[i][j],dp[i][j-1]+costErase);
                dp[i][j]=min(dp[i][j],dp[i-1][j-1]+(s1[i-1]==s2[j-1]?0:costReplace));
            }
        }
        return dp[n1][n2];
    }
};

int main(){
    LevenshteinDistance ld(1,1,1);
    int n,m; cin>>n>>m;
    string s1,s2; cin>>s1>>s2;
    cout<<ld.distance(s1,s2)<<endl;
    return 0;
}
0