자료구조] string 내에서 지정된 문자열 검색

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_STRING_SIZE 100000000
#define MAX_PATTERN_SIZE 3000

void pmatch(char*, char*);
void fail(char*);

int failure[MAX_PATTERN_SIZE];
char str[MAX_STRING_SIZE];
char pat[MAX_PATTERN_SIZE];
int set[MAX_PATTERN_SIZE];

void main()
{
errno_t err3, err4;
// FILE * pt; FILE * st;
FILE* pt; //= fopen("pattern.txt", "rt");
FILE* st; //= fopen("string.txt", "rt");
err3 = fopen_s(&pt, "pattern.txt", "rt");
err4 = fopen_s(&st, "string.txt", "rt");

if (pt == NULL || st == NULL)
{
printf("File Open Failed\n");
}
fgets(pat, sizeof(pat), pt);
fgets(str, sizeof(str), st);

fail(pat);

pmatch(str, pat);

fclose(pt);
fclose(st);
}

void fail(char *pat) {

// compute pattern's failure function 
int i, j, n = strlen(pat);
failure[0] = -1;
for (j = 1; j < n; j++) {
i = failure[j - 1];
while ((pat[j] != pat[i + 1]) && (i >= 0)) i = failure[i];
if (pat[j] == pat[i + 1]) failure[j] = i + 1;
else failure[j] = -1;
}
}


void pmatch(char *string, char *pat) {

// Knuth-Morris-Pratt string matching algorithm 

int i = 0, j = 0; int k = 0;
int rv = 0;
int lens = strlen(string);
int lenp = strlen(pat);

while (i < lens && j < lenp) {

if (string[i] == pat[j])
{
i++; j++;
if (j == strlen(pat))
{
set[k] = i - lenp; k++;
rv++;
j = 0;
i--;
}
}
else if (j == 0) i++;
else j = failure[j - 1] + 1;
}
//return ((j == lenp) ? (i - lenp) : -1);
if (rv != 0)
{
errno_t err;
FILE * re_kmp;
err = fopen_s(&re_kmp, "result_kmp.txt", "wt");

fputs("Pattern apperas ", re_kmp);
fprintf(re_kmp, " %d", k);
fputs(" times\n", re_kmp);

fputs("The pattren ", re_kmp);
fputs(pat, re_kmp);
fputs(" was found at position", re_kmp);

for (int m = 0; m < k; m++)
{
fprintf(re_kmp, " %d", set[m]);
}
fputs(" in the string.\n", re_kmp);
fclose(re_kmp);
}
else
{
errno_t err;
FILE * re_kmp;
err = fopen_s(&re_kmp, "result_kmp.txt" , "wt");
fputs("The pattern ", re_kmp);
fputs(pat, re_kmp);
fputs(" was not found in the string.\n", re_kmp);
fclose(re_kmp);
}

}