質問編集履歴

1 コードの最適化

grape_ll

grape_ll score 44

2020/07/12 22:35  投稿

編集距離の高速化の方法
### 質問内容
最初に文字列の個数が与えられて,その次の行から文字列を与えられて,それらの文字列の変種距離が10未満である組み合わせが何通りあるか答える問題なのですが,1000文字くらいの文字列が100個くらいのときに実行時間が3秒を超えてしまうのですがどのようにしたら処理を早くすることが出来ますか?
50個のケースのときには実行時間が間に合っていました.
### コード
```C
#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 length1,length2;
   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]);
   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++){
       length1=strlen(str[i]);  
       //for(y=0;y<=length1;y++) dp[0][y]=y;  
 
       for(j=i+1;j<n;j++){
           
           flag2=0;
 
           length2=strlen(str[j]);  
           //for(x=0;x<=length2;x++) dp[x][0]=x;  
           
           if(abs(length1-length2)<10){
           if(abs(length[i]-length[j])<10){
               flag2++;   //文字の長さの差が10以上ならOK
               for(x=1;x<=length2;x++){
               for(x=1;x<=length[j];x++){
               
                   flag1=0; 
               
                   for(y=1;y<=length1;y++){
                   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>=length1) break;
                   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(dp[length2][length1]<10 && flag1<length1 && flag2!=0) {
           if(flag1<length[i] && flag2!=0) {
               count++;
               //printf("%d:",dp[length2][length1]);
           }
       }
   }
   printf("%d\n",count);
   return 0;
}
```
  • C

    7332 questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

  • 最適化

    123 questions

    最適化とはメソッドやデザインの最適な処理方法を選択することです。パフォーマンスの向上を目指す為に行われます。プログラミングにおける最適化は、アルゴリズムのスピードアップや、要求されるリソースを減らすことなどを指します。

  • コードレビュー

    526 questions

    コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

思考するエンジニアのためのQ&Aサイト「teratail」について詳しく知る