#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
void generate_random_string(char *str, int length) {
const char charset[] = "abcdefghijklmnopqrstuvwxyz";
for (int i = 0; i < length; i++) {
int key
= rand() % (int)(sizeof(charset
) - 1); str[i] = charset[key];
}
str[length] = '\0';
}
char* search(char *text, char *key) {
int m, n;
char *p;
for (p = text; p <= text + m - n; p++) {
return p;
}
return NULL;
}
int main(void) {
int length = 1000000;
char *text
= (char *)malloc(length
+ 1); // 100万文字用のメモリを確保 char *key = "mouri";
char *p;
int count = 0;
// ランダムな文字列を生成
generate_random_string(text, length);
// 文字列 "mouri" を探索し、カウント
p = search(text, key);
while (p != NULL) {
count++;
printf("keyは%d桁目から%d桁目までで、それ以下の文字列は%sとなります\n", p
- text
+ 1, p
- text
+ 1 + strlen(key
), p
); p = search(p + 1, key); // オーバーラップを避けないようにポインタを1つ進める
}
printf("文字列 '%s' は生成された文字列に %d 回出現しました。\n", key
, count
);
free(text
); // 確保したメモリを解放 return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHN0cmluZy5oPgojaW5jbHVkZSA8dGltZS5oPgoKdm9pZCBnZW5lcmF0ZV9yYW5kb21fc3RyaW5nKGNoYXIgKnN0ciwgaW50IGxlbmd0aCkgewogICAgY29uc3QgY2hhciBjaGFyc2V0W10gPSAiYWJjZGVmZ2hpamtsbW5vcHFyc3R1dnd4eXoiOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBsZW5ndGg7IGkrKykgewogICAgICAgIGludCBrZXkgPSByYW5kKCkgJSAoaW50KShzaXplb2YoY2hhcnNldCkgLSAxKTsKICAgICAgICBzdHJbaV0gPSBjaGFyc2V0W2tleV07CiAgICB9CiAgICBzdHJbbGVuZ3RoXSA9ICdcMCc7Cn0KCmNoYXIqIHNlYXJjaChjaGFyICp0ZXh0LCBjaGFyICprZXkpIHsKICAgIGludCBtLCBuOwogICAgY2hhciAqcDsKICAgIG0gPSBzdHJsZW4odGV4dCk7CiAgICBuID0gc3RybGVuKGtleSk7CiAgICBmb3IgKHAgPSB0ZXh0OyBwIDw9IHRleHQgKyBtIC0gbjsgcCsrKSB7CiAgICAgICAgaWYgKHN0cm5jbXAocCwga2V5LCBuKSA9PSAwKQogICAgICAgICAgICByZXR1cm4gcDsKICAgIH0KICAgIHJldHVybiBOVUxMOwp9CgppbnQgbWFpbih2b2lkKSB7CiAgICBzcmFuZCh0aW1lKE5VTEwpKTsgLy8g5Lmx5pWw44Gu56iu44KS5Yid5pyf5YyWCiAgICBpbnQgbGVuZ3RoID0gMTAwMDAwMDsKICAgIGNoYXIgKnRleHQgPSAoY2hhciAqKW1hbGxvYyhsZW5ndGggKyAxKTsgLy8gMTAw5LiH5paH5a2X55So44Gu44Oh44Oi44Oq44KS56K65L+dCiAgICBjaGFyICprZXkgPSAibW91cmkiOwogICAgY2hhciAqcDsKICAgIGludCBjb3VudCA9IDA7CgogICAgLy8g44Op44Oz44OA44Og44Gq5paH5a2X5YiX44KS55Sf5oiQCiAgICBnZW5lcmF0ZV9yYW5kb21fc3RyaW5nKHRleHQsIGxlbmd0aCk7CgogICAgLy8g5paH5a2X5YiXICJtb3VyaSIg44KS5o6i57Si44GX44CB44Kr44Km44Oz44OICiAgICBwID0gc2VhcmNoKHRleHQsIGtleSk7CiAgICB3aGlsZSAocCAhPSBOVUxMKSB7CiAgICAgICAgY291bnQrKzsKICAgICAgICBwcmludGYoImtleeOBryVk5qGB55uu44GL44KJJWTmoYHnm67jgb7jgafjgafjgIHjgZ3jgozku6XkuIvjga7mloflrZfliJfjga8lc+OBqOOBquOCiuOBvuOBmVxuIiwKICAgICAgICAgICAgICAgcCAtIHRleHQgKyAxLCBwIC0gdGV4dCArIDEgKyBzdHJsZW4oa2V5KSwgcCk7CiAgICAgICAgcCA9IHNlYXJjaChwICsgMSwga2V5KTsgLy8g44Kq44O844OQ44O844Op44OD44OX44KS6YG/44GR44Gq44GE44KI44GG44Gr44Od44Kk44Oz44K/44KSMeOBpOmAsuOCgeOCiwogICAgfQoKICAgIHByaW50Zigi5paH5a2X5YiXICclcycg44Gv55Sf5oiQ44GV44KM44Gf5paH5a2X5YiX44GrICVkIOWbnuWHuuePvuOBl+OBvuOBl+OBn+OAglxuIiwga2V5LCBjb3VudCk7CgogICAgZnJlZSh0ZXh0KTsgLy8g56K65L+d44GX44Gf44Oh44Oi44Oq44KS6Kej5pS+CiAgICByZXR1cm4gMDsKfQ==