文字列ハッシュ・テーブルを持たないCライブラリの場合、どうすればいいのでしょうか。
C言語信頼プログラミング認定同僚はしばしば尋ねる、C言語ライブラリは、文字列のハッシュテーブル操作を持っていない、そのテストはどのように行うことが発生しました。前の試験のトピックは、C言語のハッシュテーブルのトピックを使用する必要はありませんが、また、予防措置を講じる必要がありますが、ここでは代表的なトピックは、あなたが見るために行うことを試みることができます：
文字列 s と同じ長さの単語がいくつかあるとき、words のすべての単語を連結してできる s の部分文字列の開始位置を求めなさい。
この部分文字列は、words 内の単語と、間に文字を挟まずに正確に一致しなければなりませんが、単語が連結される順序は考慮する必要がないことに注意してください。
s = "barfoothefoobarman",
words = ["foo","bar"]
[0,9]
インデックス0と9で始まる部分文字列は、それぞれ "barfoo "と "foobar "である。
出力の順番は重要ではない, [9,0] また、有効な回答もある。
プログラミング言語を考慮しないのであれば、ハッシュテーブルを使う方が簡単でしょうし、C言語を使うのであれば、自分でハッシュテーブルをジャッキアップして使えば、それでもこの種の問題に対処するには十分すぎるほどです。
If you just want to have a good hash function, and cannot wait, djb2 is one of the best string hash functions i know. it has excellent distribution and speed on many different sets of keys and table sizes.
unsigned long
hash(unsigned char *str)
{
unsigned long hash = 5381;
int c;
while (c = *str++)
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
return hash;
}
文字列ハッシュ関数を使えば、大きな文字列を数値に変換することができ、それを配列の添え字として情報を格納することができます。では、ハッシュテーブルのサイズはどのように決めればよいのでしょうか。一般的なサイズは、ハッシュテーブルに格納されている最大100個のデータなど、格納されているデータの数よりも大きくする必要があり、その後、サイズが動作するように100よりも大きくする必要があります。この質問については、明示的に単語の最大数を教えていない、唯一のハッシュテーブルのサイズを取得し、使用例の数の関係を通じて、提出テストのいくつかのラウンドの後、ここで、評価することができますこのトピックの単語の最大数は300前後かもしれないことを示唆して、<50それの平均数：
5 -> 110/173
10 -> 143/173
50 -> 170/173
100 -> 170/173
300 -> 172/173
400 -> 173/173
// 文字列の最大値、ハッシュテーブルのサイズ、評価、実際のデータ数が関係している
#define MAXWORDCOUNT 1000
static int wordCount[MAXWORDCOUNT];
static int currWordCount[MAXWORDCOUNT];
// ref: http://...ca/~oz/.html
unsigned long DJBHash(const char* s, int len) {
unsigned long hash = 5381; // 経験値、ハッシュが衝突する確率の低さ、バランスのとれた分布
while (len--) {
hash = (((hash << 5) + hash) + *(s++)) % MAXWORDCOUNT; /* hash * 33 + c */
}
return hash;
}
int* findSubstring(char * s, char ** words, int wordsSize, int* returnSize){
memset(wordCount, 0, sizeof(wordCount));
*returnSize = 0;
const int kSLen = strlen(s);
if (kSLen == 0 || wordsSize == 0) return NULL;
const int kWordLen = strlen(words[0]);
// ハッシュテーブルに単語数を保存する，key: word, value: 単語数
for (int i = 0; i < wordsSize; ++i)
++wordCount[DJBHash(words[i], kWordLen)];
int *result = malloc(sizeof(int) * kSLen);
for (int i = 0; i < kWordLen; ++i) {
for (int j = i; j + kWordLen * wordsSize <= kSLen; j += kWordLen) {
// 現在のウィンドウの単語数を数える
for (int k = (j == i ? 0 : wordsSize - 1); k < wordsSize; ++k)
++currWordCount[DJBHash(s + j + k * kWordLen, kWordLen)];
// 2つのハッシュテーブルが等しいかどうか、つまり、ウィンドウ内の単語が与えられた辞書と完全に一致するかどうかを判断する。
if (memcmp(wordCount, currWordCount, sizeof(wordCount)) == 0)
result[(*returnSize)++] = j;
--currWordCount[DJBHash(s + j, kWordLen)];
}
// ハッシュテーブルのゼロ化操作
memset(currWordCount, 0, sizeof(currWordCount));
}
return result;
}
