문자열 집합 판별

https://www.acmicpc.net/problem/9250

9250번: 문자열 집합 판별

 

Rabin-Karp Set을 사용해서 접근했음.

시간초과;;

구현이 잘못된건가ㅜ

typedef struct{
	char pattern[101];
	int length;
	int h;
	int p;
	int dp;
} rk;

rk S[1001];
int d = 25, q = 101;
int N, Q;
void gHash(int index)
{
	S[index].length = strlen(S[index].pattern);
	int i = 0, h = 0, p = 1;
	for (; i < S[index].length-1; i++)
	{
		h = (d*h + (S[index].pattern[i] - 97)) % q;
		p = (p*d) % q;
	}
	h = (d*h + (S[index].pattern[i] - 97)) % q;

	S[index].h = h;
	S[index].p = p;
}
bool compare(char* txt, int start, int index)
{
	for (int j = 0; j < S[index].length; j++)
	if (txt[start + j] != S[index].pattern[j])
		return false;
	return true;
}
bool rabin_karp(char* txt)
{
	for (int i = 0; i < N; i++)
	{
		S[i].dp = 0;
		for (int j = 0; j < S[i].length; j++)
		{
			S[i].dp = (d*S[i].dp + (txt[j] - 97)) % q;
		}
	}
	for (int i = 0; txt[i] != NULL; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (S[j].dp == -1)
				continue;
			else if (S[j].dp == S[j].h && compare(txt, i, j))
				return true;

			if (txt[i + S[j].length] != NULL)
			{
				S[j].dp = (d*(S[j].dp - (txt[i] - 97) * S[j].p) + (txt[i + S[j].length] - 97)) % q;
				if (S[j].dp < 0)
					S[j].dp += q;
			}
			else
				S[j].dp = -1;
		}
	}
	return false;
}
int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
		scanf("%s", &S[i].pattern);
		gHash(i);
	}
	scanf("%d", &Q);
	for (int i = 0; i < Q; i++)
	{
		char buff[10001];
		scanf("%s", &buff);
		printf("%s\n", (rabin_karp(buff)) ? "YES" : "NO");
	}
	return 0;
}

 

아래는 pattern 길이를 고정했음.

 

typedef struct{
	char pattern[101];
	int h;
} rk;

rk S[1001];
int p, length;
int d = 25, q = 101;
int N, Q;
void gHash(int index)
{
	length = strlen(S[index].pattern);
	int i = 0, h = 0;
	p = 1;
	for (; i < length-1; i++)
	{
		h = (d*h + (S[index].pattern[i] - 97)) % q;
		p = (p*d) % q;
	}
	S[index].h = (d*h + (S[index].pattern[i] - 97)) % q;
}
bool compare(char* txt, int start, int index)
{
	for (int j = 0; j < length; j++)
	if (txt[start + j] != S[index].pattern[j])
		return false;
	return true;
}
bool rabin_karp(char* txt)
{
	int dp = 0;
	for (int j = 0; j < length; j++)
	{
		dp = (d*dp + (txt[j] - 97)) % q;
	}

	for (int i = 0; txt[i + length-1] != NULL; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (dp == S[j].h && compare(txt, i, j))
				return true;
		}
		dp = (d*(dp - (txt[i] - 97) * p) + (txt[i + length] - 97)) % q;
		if (dp < 0)
			dp += q;
	}
	return false;
}
int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
		scanf("%s", &S[i].pattern);
		gHash(i);
	}
	scanf("%d", &Q);
	for (int i = 0; i < Q; i++)
	{
		char buff[10001];
		scanf("%s", &buff);
		printf("%s\n", (rabin_karp(buff)) ? "YES" : "NO");
	}
	return 0;
}