お詫び。

昨日ぐらいの日記に今週の金曜日が国内予選って書きましたが、、

この週末でなくて来週の週末の間違いでした(汗

この土日は新歓合宿ということで串本に潜りに行ってきます、、

どうやら天気がよくないとかなんとかでちょと心配だなぁ・・・


久々にprojectEulerを1問解きました。
http://projecteuler.net/index.php?section=problems&id=98

RACEとかCAREみたいな文字列が数千個与えられて、

その中でアナグラム(文字の入れ替えで別の単語になる)ものを

探してくるのが第一段階。さらにその各文字に0-9の数字を当てはめていく。

例えば上の例だとCに1、Aに2、Rに9、Eに6をあてはめると、

CARE=1296、RACE=9216となる。

んで実はこの2つはどちらも平方数(ある自然数の2乗した数)に

なっているんだけど(1296=36*36, 9216=96*96)、

そういうものの中で一番大きい数(この辺の詳細な定義は問題文をw)を

出してくださいとか言う問題。第2段階がちょっとてこずったけど、、

Accept(正解)もらえたときは結構すっきりしました☆



で、、第一段階のアナグラムぐらいだったら国内予選にも出そうなので、

ちょと勉強になるかなーって感じで書いてみる。といっても一瞬で終わるけど。

ある文字列A、Bが与えられたときに、それらがアナグラムか判定する

アルゴリズム(ピタゴラスイッチではなくw)を考えてくださいw

とりあえず単純で記述量が短いものを考えてみてね。答えはちょっと下に。
















正解は、文字列Aと文字列Bをソートして、その2つを直接比較する、というもの。

C++だったら

string strA,strB;
cin>>strA>>strB;
sort(strA.begin(),strA.end());
sort(strB.begin(),strB.end());
if(strA==strB)cout<<"アナグラムじゃん!"<<endl;

とまぁ上2行の入力部分を除くと3行で判定できちゃうという。

覚えておいて損はないのではないでしょうか？？

ちなみに計算量についていうと、

文字列A、Bの長さをnとしたときに、

ソートはnlognでできるので、O(nlogn)の時間で判定できます。


じゃぁ、O(n)ではできないのか考えてみましょう。

(と言うかほんとに今考えたw) O(n)でも可能ですね。

プログラムは長くなりますがソートしなければいいのです。


例えば文字列A、Bには小文字しか入らないというのであれば、

文字列に含まれる各アルファベットの数を数えたら良いですね。

コードはこちら。コンパイルしてないから間違ってるかもだけどw

string strA,strB;
cin>>strA>>strB;
int cntA[256],cntB[256];
for(int i=0;i<strA.length();i++)cntA[ strA[i] ]++;
for(int i=0;i<strB.length();i++)cntB[ strB[i] ]++;
int same=1;
for(int i=0;i<256;i++){
    if(cntA[i]!=cntB[i]){
       same=0;
       break;
    }
}
if(same)cout<<"アナグラムじゃん!"<<endl;

まぁこんな感じになると思います。

計算量はO(strA,strBの長さ+アルファベット数)になるので、

文字列の長さが短くてアルファベット数が多いときは、

ソートした方が事実上早くなるなんてこともありえます。


んー、、たまにはタメになるコンテンツも書かないとな、

と思って書いてみましたがどうでしょうかね、、

感想があったら(というかなくても)何かコメントよろしく!(笑



あ、、上では省略してしまいましたが、

strAとstrBの長さが違うときはアナグラムにはなりえません。

その場合はすぐにbreakするなり何なりして、処理を減らしましょう◎