2重ループが原因でタイムアウトになるコードを改善したい

Question

C言語初心者です。以下の問題で困っています。
（問題）
2つの英字小文字のみからなる長さがそれぞれn,mの文字列s1(文字数n),s2(文字数m)が与えられたとする。文字列s1に含まれる文字を使って文字列s2を作ろうとしたとき足りなくなる文字の個数を表示せよ。ただし文字列を構成する文字は1度のみ使うことができる。
1<=n<=100000,1<=m<=100000

たとえば文字列s1＝"catfood" s2="carrot" であるとき、s2を作るにはs1にある文字c,a,tとoが一つ使えるので必要なのはrが２つとなり出力は２になります。

これをC言語で表現しようとして考えたアルゴリズムが、文字列s2の先頭の文字から最後まで順に文字列s1の要素と比較し、等しければ両方の文字列の要素を0で上書きする。これを文字列s1の要素の最後まで行い、最後に文字列s2を出力して0でない要素の個数を出力する。
例えば上記であれば最終的にs1="000f0od" s2="00rr00"となり文字列s2の0ではない要素数である2が出力されます。

コードは以下になります。
これを実行すると小規模データは結果を出力しますがn^2のオーダーのためか要素が　100000の文字列ではタイムアウトになります。

アルゴリズムが悪いのか配列以外のデータ構造を使う必要があるのか考えてもわかりません。改善点をご教授いただければ幸いです。

#include <stdio.h>
int n,m;
char s1[100000];
char s2[100000];
//文字列s2の各要素を文字列s1の要素と比較し等しければその2つの要素を０で上書きする。
void compare(char *s1,char *s2){
    for(int i=0;i<m+1;i++){
        for(int j=0;j<n+1;j++){
            if(s2[i]==s1[j]){s2[i]=s1[j]='0';}
        }
    }
}
//改変された文字列s2の要素のうち0でないものの個数をカウントする。
int count(char *s2){
    int counter=0;
    for(int i=0;i<m+1;i++){
        if(s2[i]!='0')counter+=1;
    }
    return counter;
}

int main(void){
    scanf("%d %d",&n,&m);
    scanf("%s",s1);
    scanf("%s",s2);
    compare(s1,s2);
    printf("%d\n",count(s2));
    return 0;
}

Comments

[Orlofsky]

コードは https://teratail.com/help/question-tips#questionTips3-7 の [コード] に修正してください。

[qazwsx_0000]

申し訳ありません。
所定の場所に移しました。

Answer 1

そのコードでは s1＝"catfood" s2="carroot" の時は幾つになるでしょう.

100000文字は試していません.

#include <stdio.h>
#include <string.h>

//'a'～'z'
#define SIZE 26

int main(void) {
  char *s1="catfood";
  char *s2="carrot";

  int a1[SIZE]={0};
  int l1=strlen(s1);
  for(int i=0;i<l1;i++) a1[s1[i]-'a']=1; 

  int a2[SIZE]={0};
  int l2=strlen(s2);
  for(int i=0;i<l2;i++) a2[s2[i]-'a']++;

  int r=0;
  for(int i=0;i<SIZE;i++) if(a2[i]>a1[i]) r+=a2[i]-a1[i];
  printf("%d\n",r);

  return 0;
}

Comments

[kazuma-s]

タイムアウトが問題なのに、forループの中で strlen を繰り返し呼び出すのはいかがなものでしょうか？
s1 には o が 2つあるので、s2 に o が 2つあってもよいのではないでしょうか？

[jimbe]

>forループの中で strlen を繰り返し呼び出す
見えない多重ループになっているということですね.
修正致しました.

>s1 には o が 2つあるので、s2 に o が 2つあってもよいのでは
>>s2を作るにはs1にある文字c,a,tとoが一つ使える
と言われているので, s2 に o が2つあった場合は1つ不足としてカウントされるのではないかと思った次第です.

[qazwsx_0000]

このコードを改変して投稿すると文字列数100000でも0.01秒にて実行されました。
他の方も言われているようにアルファベットのみの文字列であることを利用することで高速化が図れるようです。
ありがとうございました。

Answer 2

各文字ごとの個数だけわかれば計算できます。出現位置の情報は無視していいということです。そうすると線形時間で処理できます。

s1とs2ごとに文字:出現数の表を作って、その間で差分を取り（table2[char_i] - table1[char_i]のような形で。ただしマイナスになったら0とみなす）合計するのでしょう。

Pythonでサンプルを示します。

from collections import Counter

s1 = "catfood"
s2 = "carrot"

table1 = Counter(s1)
table2 = Counter(s2)

# 確認
print(table1)
print(table2)

for key in table2.keys():
    x = table2[key] - table1[key]
    table2[key] = max(x, 0)

# 確認
print(table2)

# 結果
print(sum(table2.values()))

""" =>
Counter({'o': 2, 'c': 1, 'a': 1, 't': 1, 'f': 1, 'd': 1})
Counter({'r': 2, 'c': 1, 'a': 1, 'o': 1, 't': 1})
Counter({'r': 2, 'c': 0, 'a': 0, 'o': 0, 't': 0})
2
"""

Cで実装する場合、出現する文字がASCIIだけなら、128要素の整数型配列を使うことができます。マルチバイト文字ならデータ構造を工夫した方が賢いでしょう。

Comments

[qazwsx_0000]

出現する文字数を格納する配列を作るとうまく解決しました。
またpythonのCounter関数は勉強になりました。

Answer 3

改善点をご教授いただければ幸いです。

のご要望にお応えしていませんが、見つけたら配列から削除する方式です

#include <stdio.h>
#include <string.h>

char n[100000];
char m[100000];

int main(){
    memset(n, '\0', sizeof(n));
    memset(m, '\0', sizeof(m));

    printf("文字列[n]:");
    fgets(n, sizeof(n), stdin);
    n[strlen(n)-1]='\0';
    printf("文字列[m]:");
    fgets(m, sizeof(m), stdin);
    m[strlen(m)-1]='\0';
    printf("n:%s\n",n);
    printf("m:%s\n",m);

    int i, j, cnt=0, flg;
    for(i=0;i<strlen(m);i++){
        flg=1;
        for(j=0;j<strlen(n);j++){
            if(m[i] == n[j]){
                strcpy(n+j,n+(j+1));
                flg=0;
                break;
            }
        }
        cnt+=flg;
    }
    printf("count:%d\n",cnt);
    return 0;
}

ご指摘を受けて修正版

#include <stdio.h>
#include <string.h>

char n[100001];
char m[100001];
char z[100001];

int main(){
    memset(n, '\0', sizeof(n));
    memset(m, '\0', sizeof(m));

    scanf("%s", n);
    scanf("%s", m);

    int i, j, cnt=0, flg;
    int x=strlen(m);
    int y=strlen(n);
    printf("n:%d\n",x);
    printf("m:%d\n",y);

    for(i=0;i<x;i++){
        flg=1;
        for(j=0;j<y;j++){
            if(m[i] == n[j]){
                strcpy(z,n+(j+1));
                strcpy(n+j,z);
                y--;
                flg=0;
                break;
            }
        }
        cnt+=flg;
    }
    printf("count:%d\n",cnt);
    return 0;
}

私の貧富マシンでも100000件を1分程度で終了しました。

Comments

[kazuma-s]

タイムアウトが問題なのに、forループの中で strlen を繰り返し呼び出すのはいかがなものでしょうか？

[qazwsx_0000]

このコードでも100000の文字列を30秒でクリアします。私のコードは3分以上かかるようです。
教えていただきたいのですが、私のコードでもこのコードでもfor文を用いた2重ループで、私の場合配列の上書き、このコードの場合配列をずらしています(コピーしています）。ループの最後に行う処理はあまり違いがないように思うのですが私のコードで3分以上かかる処理をこのコードが早く処理できるのはなぜなのでしょうか？

[amura]

多分strcpyでのデータ移動の方が効率が良かったのではないでしょうか？
strcpyは1バイトづつの転送ではないらしく、最初のプログラムで10万件行うと答えが変になります。後のプログラムでは2回コピーしています。

[qazwsx_0000]

確かに私の環境でも最初のコードは大規模データで失敗しました。strcpyのマニュアルをみると「コピー元とコピー先が重なり合う場合動作が未定義」とありますが、大規模データでのバグに関係しているかもしれませんね。
他の方のアルファベットの特性を利用したコードがこの問題の正解に近いものだとは思いましたのでベストアンサーにしましたが、amuraさんのコードは非常に勉強になりました。ありがとうございました。

Answer 4

ルールの内で時間を短縮するのに有用なのは

• 英字小文字のみからなる
• 文字列を構成する文字は1度のみ使うことができる

ですね。

s1 がどれだけ長かろうと出来上がる情報量は 26bit (英字小文字は 26 文字なので) しかありません。 一度しか使えないので何度現れても「使われているかどうか」だけの情報があればよいのです。

• まずは s1 を走査して各アルファベットが使われているかどうかを調べる
• 調べた値が s2 にも出現しているか調べる
• s1 にも s2 にも表れている文字種の数を s2 の長さから引く

でどうでしょう。

これなら O(n+m) のオーダーで解決できると思うのですが。

Comments

[qazwsx_0000]

確かに英字小文字のみという条件でしぼると解決できます。
ありがとうございました。