-1

あなたの最高の文字列比較アルゴリズムは何ですか?

O(n) を見つける

#include <string>

bool str_cpmr(char* str1, char* str2)
{
    int l1 = strlen(str1), l2 = strlen(str2) ;          

    if(l1 != l2)
        return false;

    for(int i = 0 ; i < l1 ; i++)
        if(str1[i] != str2[i])
            return false ;

    return true ;
}

他の/より良い解決策があるのではないかと思います。

また、それを正確にテストする方法は？

私は比較することを提案します

  • 100試合
  • 1 文字のスワップが異なる 100 個の文字列

文字列比較をテストするものは他にありますか?

stl c++ (slt string::compare) ではどうですか?

ありがとう！！！！！

4

5 に答える 5

4

関数は O(n) ですが、必要な時間が約 2 倍かかりますstrlen。文字列を調べて長さを見つけ、(同じ長さであると仮定して) 文字列をもう一度比較して文字列を調べます。

その代わりに、不一致または両方の文字列の終わりに到達するまで、文字列をウォークスルーします。不一致に達した場合は、false を返します。最初に不一致がなく、両方の文字列の末尾に (同時に) 到達した場合にのみ、true を返します。

于 2012-10-10T16:39:48.663 に答える
3

論理的には、文字列に関する他の情報がないと仮定すると、文字列内のすべての値を O(n) 時間未満で 1 つの文字の不一致についてチェックする方法を理解するのは困難です。

これが実際のアプリケーションであり、文字列と違いのタイプについてある程度の知識がある場合、部品番号や電話番号などの長さ「N」のシーケンスが含まれていることがわかっている場合は、N 番目の文字ごとに最初にチェックすることで、平均してより良い結果が得られます。

編集:これはまだ O(n) であることに注意してください。O() はスケーリングの力のみを表します。それは O(n/N) であり、これはまだ O(n) です。文字列を 10 倍長くしても、N 番目のエントリごとにチェックするのに 10 倍の時間がかかります。

于 2012-10-10T16:38:29.990 に答える
3

あなたの最高の文字列比較アルゴリズムは何ですか?

template< class T, class Alloc > bool operator==( basic_string<T,Alloc>& lhs, basic_string<T,Alloc>& rhs );.

ソース コードの 2 文字のみを使用して 2 つの文字列を比較します。

a==b;

Cで書かれたsmartalec以外の回答は次のとおりです。

bool str_cpmr(char* str1, char* str2)
{
  while( *str1 && *str2 && *str1++ == *str2++ )
    ;
  return *str1 == *str2;
}

これは正確に 1 つのループなので、明らかに O(n) です。ここで、n は短い文字列の長さです。また、正確に 2n 回のメモリ フェッチにコンパイルされる可能性があります。特殊な文字列命令を使用すると高速化できます (したがって、strcmp() の呼び出しはおそらくこれよりも高速になります) が、単純な C ではおそらく高速化されません。

于 2012-10-10T16:41:15.417 に答える
2

改善された関数は次のようになります。

bool str_cpmr(char* str1, char* str2)
{
    if (NULL == str1 || NULL == str2) return false;

    while (*str1 && *str2) {
        if (*str1++ != *str2++) {
            return false;
        }
    }

    return *str1 || *str2 ? false : true;
}
于 2012-10-10T16:46:59.633 に答える
2

文字列の性質に関する追加情報がない場合、O(n) よりも優れたものはありません。ここで、n は (短い) 文字列の長さです。

n回未満の比較ではできません! n-1 回の比較でそれを実行できるアルゴリズムを教えてください。次に、文字が異なるかどうかをアルゴリズムが判断できない文字列内の位置が必要です。そうすれば、n-1 比較によるアルゴリズムが失敗する例を示すことができます。

これを改善できるのは一定の係数だけです。これには、追加情報も考慮されます。たとえば、基礎となるハードウェアが 8 ビット値よりも 32 ビット値を高速に比較することがわかっている場合、文字ごとに比較するのではなく、4 文字のチャンクを比較する方が適切です。あなたはそれほどうまくやることはありません。

于 2012-10-10T16:51:52.190 に答える