글 읽기 - 살려주세요 고수님들...

average10 4년 전 0

처음엔 kmp로 시도했다가 실패하고

라빈 카프로도 시도했다가 다 짜고보니 라빈 카프도 문자열의 순서가 맞아야 하는 알고리즘이더군요...

그냥 아스키값 빼고 더할까 했지만 ad와 bc는 합이 같으니 그냥 아무수 곱해서 더한걸로도 해도 틀리고...

도대체 어찌 푸는 문제인가요 ㅜㅜㅜ 미치겠습니다

#include <iostream>
#include <string>
#include <math.h>
using namespace std;

int g, s;
long long patternVal, Sval, cnt;
string W, S;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> g >> s;
    cin >> W >> S;

    for(int i=0;i<g;i++) {  //W에 대한 hash 값
        patternVal += W[i]*17 + 34;
    }

    for(int i=0;i<g;i++) {  //S의 hash 초기값
        Sval += S[i]*17 + 34;
    }
    if(patternVal == Sval) cnt++;   //초기값 일치여부 확인
    for(int i=g;i<s;i++) {
        Sval += S[i]*17+34 - (S[i-g]*17+34);
        if(Sval == patternVal) cnt++;
    }
    cout << cnt;

    return 0;
}

sait2000 4년 전 0

나올 수 있는 문자의 종류가 적으니까 각 문자의 개수를 세면 됩니다.

average10 4년 전 0

@sait2000

아.... 정답률이 높다 했더니 제가 문제를 너무 어렵게 생각했군요..

정말 감사합니다 갓갓형님 ㅠㅠㅠ 해결했습니다

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

문제

문제

출처

ICPC

살려주세요 고수님들...

average10 4년 전 0

sait2000 4년 전 0

average10 4년 전 0

@sait2000

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말