はじめに
学校の課題でホールスプール法を用いた文字列照合の実装が出ました。
ASCIIコードでチャチャっと実装しちゃうこともできるのですが、せっかくC言語なのでポインタ使ってゴリゴリに書きたいと思いました。そこで、連想配列をフルスクラッチで実装することで、あえてASCIIコードを使わないホールスプール法の実装に成功しました！嬉しかったので記録しておきます。
出力結果
"she sells sea shells on the sea shore"というテキストから"shell"という文字列を照合しました。また、照合の過程や連想配列の中身も確認できるように出力しました。
コード全文
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define P_BUCKET_SIZE 10 // ハッシュ表の大きさ
#define S_BUCKET_SIZE 10 // ハッシュ表の大きさ
typedef char KEY; // キーの型
/* データ部（キー以外）のフィールド */
typedef struct data
{
int value;
} DATA;
/* データ一つを表すレコード */
typedef struct record
{
KEY key;
DATA data;
struct record *next;
} RECORD;
/* グローバル変数 */
RECORD *p_table[P_BUCKET_SIZE];
RECORD *s_table[S_BUCKET_SIZE];
/*ハッシュ表の初期化*/
void init()
{
int i;
for (i = 0; i < P_BUCKET_SIZE; i++)
p_table[i] = NULL;
for (i = 0; i < S_BUCKET_SIZE; i++)
s_table[i] = NULL;
}
/*ハッシュ関数*/
int hash(KEY key)
{
return key % 10;
}
/*key1とkey2が等しいかどうか。等しいなら１, 等しくないなら０を返す*/
int keyequal(KEY key1, KEY key2)
{
return key1 == key2;
}
DATA *search(RECORD **table, KEY key)
{
RECORD *p;
int index;
index = hash(key); // keyのハッシュ値を求める
/*連結リストをたどる*/
for (p = table[index]; p != NULL; p = p->next)
{
if (keyequal(key, p->key))
return &p->data; // 発見=>DATAへのポインタを返す
}
return NULL; // 見つからない時にはNULLを返す
}
int add(RECORD **table, RECORD *record)
{
RECORD *p;
int index;
if (search(table, record->key) != NULL)
{
return -1;
}
p = (RECORD *)malloc(sizeof(RECORD));
if (p == NULL)
{
perror("out of memory.\n");
exit(1); // プログラムを強制終了
}
/*ハッシュ関数でrecord.keyのハッシュ値を求める*/
index = hash(record->key);
p->key = record->key;
p->data = record->data;
/* table[index]に新しく作成したレコードを挿入する*/
p->next = table[index];
table[index] = p;
return 0;
}
void p_createMap(RECORD **table, char P[], int length)
{
printf("✅ p_createMap\n");
int i = 0;
for (i = 0; i < length; i++)
{
if (search(table, P[i]) == NULL)
{
DATA data;
data.value = length - i - 1;
RECORD record;
record.key = P[i];
record.data = data;
add(table, &record);
}
}
}
void s_createMap(RECORD **table, char S[], int s_length, int p_length)
{
int i = 0;
printf("✅ s_createMap\n");
for (i = 0; i < s_length; i++)
{
if (search(table, S[i]) == NULL)
{
DATA data;
DATA *pData = search(p_table, S[i]);
if (pData != NULL)
{
data.value = pData->value;
}
else
{
data.value = p_length;
}
RECORD record;
record.key = S[i];
record.data = data;
add(table, &record);
}
}
}
int main()
{
// テキスト
char *T = "she sells sea shells on the sea shore";
// パターン
char *P = "shell";
int n = strlen(T); // テキストの文字数
int m = strlen(P); // パターンの文字数
int i = 0; // テキストに対して照合を行う位置の先頭
int j = 0; // パターンに対して照合を行う位置
int times = 0;
init();
p_createMap(p_table, P, m);
for (int i = 0; i < P_BUCKET_SIZE; i++)
{
RECORD *p = p_table[i];
while (p != NULL)
{
printf("Key: '%c', Value: %d\n", p->key, p->data.value);
p = p->next;
}
}
s_createMap(s_table, T, n, m);
for (int i = 0; i < S_BUCKET_SIZE; i++)
{
RECORD *p = s_table[i];
while (p != NULL)
{
printf("Key: '%c', Value: %d\n", p->key, p->data.value);
p = p->next;
}
}
i = 0;
while (i < n - m + 1)
{
printf("%d", i);
if (i < 10)
printf(" ");
else
printf(" ");
j = m - 1;
while (j >= 0 && T[i + j] == P[j])
{
if (j - (m - 1) != 0)
printf(" ");
printf("%s\n", T);
for (int k = 0; k < i + j + 3; k++)
printf(" ");
printf("+\n");
for (int k = 0; k < i + 3; k++)
printf(" ");
printf("%s\n\n", P);
j--;
times++;
}
if (j == -1)
{
printf("テキスト index=%dの位置にパターン%sがありました\n", i, P);
printf("比較回数は%dでした\n", times);
return 0;
}
else
{
if (j - (m - 1) != 0)
printf(" ");
printf("%s\n", T);
for (int k = 0; k < i + j + 3; k++)
printf(" ");
printf("|\n");
for (int k = 0; k < i + 3; k++)
printf(" ");
printf("%s\n\n", P);
i += search(s_table, T[i + (m - 1)])->value;
times++;
}
}
printf("❎ パターンが見つかりませんでした\n");
printf("比較回数は%dでした\n", times);
return 0;
}
最後に
フルスクラッチは難しいからこそ、欲しい結果が得られた時の達成感が気持ちいですよね。これからもアルゴリズムの勉強頑張ります！