被らない文字の個数判定の高速化

Question

半角英小文字で構成される文字列が2つあり、1つめには無く2つめにはある文字の数を調べるプログラミングを作りました。なお1:1対応なので同じ文字が複数あっても2つめのほうが多い場合剰余分がカウントされます。

例）abc,bca → 0, abcd,dcaae → 2

方法は一致したら大文字に変え最終的に小文字の個数を調べるのですが、文字数が増えるとどうしても処理が遅くなってしまいます。どうにか高速化する方法はないでしょうか？

#include <stdio.h>
#include <ctype.h>
int main(void){
    int a,b,i,j,k,n=0;
    char s[10000],t[10000];
    scanf("%d %d",&a,&b);    //文字数の入力
    scanf("%s",s);    //1つめの文字列
    scanf("%s",t);    //2つめの文字列
    for(i=0;i<a;i++){
        for(j=0;j<b;j++){
            if(s[i]==t[j]){
                t[j]=toupper(t[j]);     //被ったら大文字に
                break;
            }
        }
    }
    for(k=0;k<b;k++){
        if(islower(t[k])!=0) {n+=1;}    //小文字の個数判定
    }
    printf("%d",n);
    return 0;
}

Answer 1

アルファベットは26文字しかないので先にカウンター配列を用意しておくといいともいますよ。

カウンター配列定義
char count[256];//なお、各要素を0で初期化しておく。

文字列2を一文字ずつ読み取ってその場所のカウンターをインクリメントしていく
count[t[i] ]++;

文字列1を一文字ずつ読み取ってその場所のカウンターをデクリメントしていく
count[s[i] ]--;

countが1以上である要素数を調べて出力

こんな感じでどうでしょう。動作未検証

Comments

[HogeAnimalLover]

本方法であれば時間計算量はO(N + M)となります。ここでN、Mは文字列１、２の長さです。ご提示の方法はO(NM）なので時間はかなり節約できます。カウンター配列を要する分、メモリ空間コストがかかりますが、増分は固定256バイトなので大した問題にはならないと思います。

[hirohiro]

おお、これは凄い。
abcd,aaaa → 3 こういう仕様みたいなので、1以上の要素の合計を出せば良さそうですね。

[masaya_ohashi]

私もこのやり方で例のあの問題を解きました。
私はint[26]で配列を作り、t[i]-'a'といった具合に0-25の添字に変換してカウントしました

[suzaria]

なるほど！
文字毎にカウントすれば楽にできそうですね、目から鱗です...
ありがとうございました！

[catsforepaw]

s,tそれぞれ配列のサイズが10000あるので、count配列がcharでは桁あふれを起こす可能性があります。masaya_ohashi さんのようにintにした方が良いですね（shortでも良いですが）。

[HogeAnimalLover]

>>catsforepawさん
おお、確認していませんでした。フォローありがとうございます。