글 읽기 - 1786번 질문입니다

pkc4913 5년 전 0

라빈 카프 알고리즘으로 풀어보려고 했지만 틀렸습니다

어디가 틀린걸까요..?

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <string.h>
#define MAXSTRING 1000001
using namespace std;


class Karprabin {
private:
	char* text;
	char* pattern;
	int textsize;
	int patternsize;
	int coeff;

	int hash(char *s) {
		int hashvalue = 0;
		for (int i = 0; i < patternsize; i++) {
			hashvalue += s[i] * pow(2.0, patternsize - (1 + i));
		}
		return hashvalue;
	}

	int rehash(int start,int hashprev) {
		if (start == 0) return hashprev;
		return text[start + patternsize - 1] + ((hashprev - coeff * text[start - 1]) * 2);
	}
	
public:

	Karprabin(char *text, char* pattern) {
		this->text = text;
		this->pattern = pattern;
		this->textsize = strlen(text);
		this->patternsize = strlen(pattern);
		this->coeff = pow(2.0, patternsize - 1);
	}

	vector<int> karprabinHash() {
		int hashText = hash(text);//patternsize 만큼 hash
		int hashPattern = hash(pattern);
		vector<int> v;
		for (int i = 0; i <= textsize - patternsize; i++) {
			hashText = rehash(i, hashText);
			if (hashText == hashPattern) {
				int j;
				for (j = 0; j < patternsize; j++) {
					if (text[i + j] != pattern[j]) break;
				}
				if (j >= patternsize) v.push_back(i + 1);
			}
		}
		return v;
	}
};

char text[MAXSTRING];
char pattern[MAXSTRING];
int main() {

	cin.getline(text, MAXSTRING, '\n');
	
	cin.getline(pattern, MAXSTRING, '\n');
	Karprabin mykarp(text, pattern);
	vector<int> v = mykarp.karprabinHash();
	printf("%d\n", v.size());
	for (int i = 0; i < v.size(); i++) {
		printf("%d\n", v[i]);
	}
}

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

문제

문제

출처

ICPC

1786번 질문입니다

pkc4913 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말