글 읽기 - c++, 문자열 슬라이드 문제, 왜 오답일까요?

choihj105 1년 전 0

Rabin-karp 방법을 이용하여 포함 여부를 구하려고 하였는데 어떤점에서 오류가 나는지 도통 모르겠습니다.

풀이 전략은 해쉬값을 이용하여 시간복잡도 O(n)으로 구하는 것입니다.

#include <iostream>
#include <functional>
#include <string>
using namespace std;

int main() {
	string s, k, str;
	cin >> s >> k;
	
	hash<string> str_hash;
	int ans = str_hash(k);

	// 숫자를 뺀 문자열 str
	for (int i = 0; i < k.size(); i++) str += s[i];
	
	// s의 각 인덱스마다, 해쉬를 이용하여 포함된지 구하기
	bool flag = false;
	for (int i = 0; i < str.size() - k.size() + 1; i++) {

		if (ans == str_hash(str.substr(i, k.size()))) {
			
			flag = true;
			// 해쉬값이 중복일 경우 한 번 더 체크
			for (int j = 0; j < k.size(); j++) {
				if (str[i + j] != k[j]) {
					flag = false;
					break;
				}
			}
			break;
		}
	}

	cout << flag;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c++, 문자열 슬라이드 문제, 왜 오답일까요?

choihj105 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말