質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.92%

編集距離の高速化の方法

解決済

回答 1

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 279

grape_ll

score 38

質問内容

最初に文字列の個数が与えられて,その次の行から文字列を与えられて,それらの文字列の変種距離が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;

}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

checkベストアンサー

+1

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

2つの文字列S,Tの長さをlen_s,len_tとし、任意のi文字目(1 <= i <= len_s かつ len_t)までの文字列をSi,Tiとすると、SiTiのレーベンシュタイン距離が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で回していた灰色の部分は計算しなくても済みます。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/07/12 22:10

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

    キャンセル

  • 2020/07/12 22:13

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

    キャンセル

  • 2020/07/12 22:50

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.92%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る