글 읽기 - 1786 5%에서 틀렸습니다가 뜹니다.

heratkfkdgo 3년 전 0

라빈 카프로 짰는데 5%에서 틀렸습니다가 뜹니다. 백준 질문에 나와있는 반례는 다 넣어봤어요.

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
#define MAXN 10000000
char T[MAXN+2],P[MAXN+2];
using namespace std;
long long int MOD=900000000000000000;
long long int count=0,pl;
vector<int> V;

long long int mod(long long int x)
{
	if(x>=0) return x%MOD;
	else return ((-x/MOD+1)*MOD+x)%MOD;
}

void compare(int x)//T의 x번째부터와 P를 비교
{
	for(int i=x;i<x+pl;i++)
	{
		if(T[i]!=P[i-x])
			return;
	}
	count++;
	V.push_back(x+1);	
} 
int main()
{
	cin.getline(T,MAXN+1,'\n');
	cin.getline(P,MAXN+1,'\n');
	pl=strlen(P);
	
	long long int hp=0,ht=0;
	long long int pow=1,i=0;
	for(i=pl-1;i>=0;i--)
	{
		pow=mod(pow*2);
		hp=mod(hp+(int)P[i]*pow);
		ht=mod(ht+(int)T[i]*pow);
	}
	if(hp==ht) compare(0);
	for(i=pl;T[i]!='\0';i++)
	{
		ht=mod((ht-(int)T[i-pl]*pow)*2+(int)T[i]*2);
		if(hp==ht) compare(i-pl+1);
	}	
	
	printf("%d\n",count);
	for(int i=0;i<V.size();i++)
		printf("%d ",V[i]);
	return 0;
}

gomjellie 3년 전 0

pow (제곱수) 만들때 2의 제곱으로 하지말고 더 큰값의 제곱수를 써보세요

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

문제

문제

출처

ICPC

1786 5%에서 틀렸습니다가 뜹니다.

heratkfkdgo 3년 전 0

gomjellie 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말