編集距離の高速化の方法

Question

質問内容

最初に文字列の個数が与えられて，その次の行から文字列を与えられて，それらの文字列の変種距離が10未満である組み合わせが何通りあるか答える問題なのですが，1000文字くらいの文字列が100個くらいのときに実行時間が3秒を超えてしまうのですがどのようにしたら処理を早くすることが出来ますか？
50個のケースのときには実行時間が間に合っていました．

コード

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define MN3(o,p,q)((o)<(p)?((o)<(q)?(o):(q)):((p)<(q)?(p):(q)))
#pragma GCC optimize("O3")
char str[100][1001];
int main(void){
    int n;
    scanf("%d",&n);
    int count=0;
    int i,j,x,y,k,l;
    int length[100];
    int dp[1001][1001];
    int cost;
    int flag1=0,flag2=0;;
   

    dp[0][0]=0;

    for(i=0;i<n;i++) {
        scanf("%s",str[i]);
        length[i]=strlen(str[i]);
    }

    for(y=0;y<=1000;y++) dp[0][y]=y; 
    for(x=0;x<=1000;x++) dp[x][0]=x;

    for(i=0;i<n-1;i++){

        for(j=i+1;j<n;j++){
            
            flag2=0;
            
            if(abs(length[i]-length[j])<10){
                flag2++;    //文字の長さの差が10以上ならOK
                for(x=1;x<=length[j];x++){
                
                    flag1=0;  
                
                    for(y=1;y<=length[i];y++){
                        if(str[i][y-1]!=str[j][x-1]) cost=1;
                        else cost=0;
                        dp[x][y]=MN3(dp[x-1][y]+1,dp[x][y-1]+1,dp[x-1][y-1]+cost);
                        if(dp[x][y]>9) flag1++; //下のifと合わせて使う幅の行成分が全部10以上ならOUTにする
                    }
                
                    if(flag1>=length[i]) break;
                
                }
            }

            
            
            /*
            for(k=0;k<=length2;k++){
                for(l=0;l<=length1;l++){
                    printf("%d ",dp[k][l]);
                }
                printf("\n");
            }
            */
            
            if(flag1<length[i] && flag2!=0) {
                count++;
                //printf("%d:",dp[length2][length1]);
            }
        }
    }
    printf("%d\n",count);
    return 0;

}

Answer 1

実際にコードで試していないのでどれだけ早くなるかは未知数ですが・・・

2つの文字列S,Tの長さをlen_s,len_tとし、任意のi文字目(1 <= i <= len_s かつ len_t)までの文字列をSi,Tiとすると、SiとTiのレーベンシュタイン距離が10-abs(len_s-len_t)未満であれば合格と考えることができます。
つまりdp[1][1],dp[2][2]...と調べていき、最初に閾値以上が出た時点で不合格とすれば良いです。
次に、例えばdp[2][2]を求めるためにはdp[1][1],dp[2][1],dp[1][2]が必要です。これらを求めるには添え字が0～2の9要素がわかっていれば求まります。
同様に、dp[3][3]を求めるには添え字が0～3の16要素がわかっていれば求まります。
すなわち、dp[i][i]を求めるなら添え字0～iまでの数値がわかっているだけで良く、0～len_sまで走査する必要はありません。

例えば閾値が3で"vintner"と"writers"を比較するような場合。

レーベンシュタイン距離を実際に計算する範囲は黄色の領域で、質問のコードのようにforで回していた灰色の部分は計算しなくても済みます。

Comments

[grape_ll]

length1のfor文の上にsa=abs(length1-length2)を入れて
if(dp[x][y]>9-sa) flag1++;
としたら答えが一致しなくなってしまったので訂正の仕方が違うと思うのですが具体的にどのように改善すればいのか教えていただけませんか．

[hope_mucci]

NGになる具体的なテストケースを教えていただければ検証します。お願いします。

[grape_ll]

返信遅れてしまい申し訳ございません．
いかにテストケースを貼りたいと思います．一つ目は，元のコードでも三秒以内に正解を出すことが出来ます．
二つ目は実行時間オーバーになってしまいます．
また上述した私の訂正をすると，両社とも不正解になりそうです．(二つ目のほうは結果が表示されなかったのでわかりませんが，あっていた二つが不正解になってしまったのでおそらく不正解だと思います)

[grape_ll]

文字数オーバーになってしまうので質問のところに記載します．
よろしくお願いします．

[grape_ll]

文字数が上限をオーバーしてしまって質問のほうにも張ることが出来ませんでした．
どのように共有いたしましょう．

[grape_ll]

今更の疑問で申し訳ないのですが，灰色の部分は結局どこの(i,i)で終わりにすればいいのか分からない状態では，dp行列の成分を全て埋めたうえで対角成分を見るしかないのではないかと思ったのですが，どうでしょうか．
理解が追い付いていないのかもしれません．よろしくお願いします．