3

たとえば。単語はforで、テキストはforxxorfxdofr、アナグラムは、、などforになります。したがって、この特定の例に対する答えは次のようになります。ofrorffro3

これが私が思いついたものです。

#include<iostream>
#include<cstring>

using namespace std;

int countAnagram (char *pattern, char *text)
{
    int patternLength = strlen(pattern);
    int textLength = strlen(text);

    int dp1[256] = {0}, dp2[256] = {0}, i, j;

    for (i = 0; i < patternLength; i++)
    {
        dp1[pattern[i]]++;
        dp2[text[i]]++;
    }

    int found = 0, temp = 0;

    for (i = 0; i < 256; i++)
    {
        if (dp1[i]!=dp2[i])
        {
            temp = 1;
            break;
        }
    }

    if (temp == 0)
        found++;


    for (i = 0; i < textLength - patternLength; i++)
    {
        temp = 0;
        dp2[text[i]]--;
        dp2[text[i+patternLength]]++;
        for (j = 0; j < 256; j++)
        {
            if (dp1[j]!=dp2[j])
            {
                temp = 1;
                break;
            }
        }
        if (temp == 0)
            found++;
    }
    return found;
}


int main()
{
    char pattern[] = "for";
    char text[] = "ofrghofrof";

    cout << countAnagram(pattern, text);

}

上記の問題に対するより高速なアルゴリズムはありますか?

4

3 に答える 3

0

乗算の可換性と、原始分解の一意性を使用できます。これは、ここでの私の以前の回答に依存しています

各文字から素数のリストへのマッピングを作成します (できるだけ小さくします)。たとえば、a-->2、b-->3、c-->5 など。これは単純な配列に保持できます。

次に、指定された単語を、その各文字に一致する素数の乗算に変換します。この結果は、その単語のアナグラムの同様の乗算に等しくなります。

次に、配列全体をスイープし、任意のステップで、最後の L 文字 (L は単語の長さ) に一致する素数の乗算を維持します。だからあなたが前進するたびにあなたはそうします

mul = mul * char2prime(text[i]) / char2prime(text[i-L])

この乗算が単語の乗算と等しいときはいつでも - 全体のカウンターをインクリメントすれば完了です。

この方法は短い単語ではうまく機能しますが、素数の乗算は 64b var をかなり速くオーバーフローさせる可能性があることに注意してください (~9 ～ 10 文字)。そのため、長い単語をサポートするには多数の数学ライブラリを使用する必要があります。

于 2013-10-04T04:59:08.780 に答える
0

ほとんどの時間は検索に費やされるため、アルゴリズムの時間をより効率的にするための目的は、検索の量を減らすか、検索を最適化することです。

方法 1: 検索開始位置のテーブル。

アルファベットの各文字に対して 1 つのベクトル スロットである、リストのベクトルを作成します。これは後でスペースを最適化できます。

各スロットには、テキストへのインデックスのリストが含まれます。

テキスト例:forxxorfxdofr 

Slot  List  
'f'    0 --> 7 --> 11  
'o'    1 --> 5 --> 10  
'r'    2 --> 6 --> 12

単語ごとに、ベクトル内の文字を検索して、テキスト内のインデックスのリストを取得します。リスト内のインデックスごとに、リスト項目から単語までのテキスト文字列の位置を比較します。

したがって、上記の表と「ofr」という単語を使用すると、最初の比較はインデックス 1 で発生し、2 回目の比較はインデックス 5 で発生し、最後の比較はインデックス 10 で発生します。

(インデックス + 単語の長さ > テキストの長さ) のテキスト インデックスの近くを削除できます。

于 2013-10-03T19:28:10.820 に答える