백준 1543번 - 문서 검색

백준 1543번 - 문서 검색

www.acmicpc.net/problem/1543

1543번: 문서 검색

최근에 KMP알고리즘에 대해 공부 한 뒤라 자신 있게 풀어보려 들어갔다.

문제 n제한과 시간 제한을 보니 KMP 쓰기에도 아깝다고 생각이 들었다.

 

가볍게 브루트포스로 풀고 넘어가려 했는데...

반전!! 삐빅!! 틀렸습니다. 삐빅!! 런타임 에러.

 

하... 역시 문제는 풀어도 풀어도 어렵다...

실버 4 문제라고 절대 방심해선 안된다는 걸 깨달았다.

 

처음 틀렸습니다는 내가 문제를 제대로 안 읽고 중복을 계산하지 않아서 틀렸다ㅋㅋㅋ

 

다음의 런타임 에러는 아마 많은 사람들?(나만 그럴 수도)이 발생할 거 같은데

이유는 비교할 문자열이 더 길 수도 있다!!!

 

사실 진짜 당연한 건데 항상 놓치는 거 같다..

이거 때문에 20분 넘게 고민하고 있었다.. 코드는 완벽한데 뭐가 문젤까....

쨌든 질문검색에도 쓰여있지 않은 꿀팁? 인 듯

 

#include <iostream>
#include <string>
using namespace std;
 
int main() {
    string origin, cmp;
    getline(cin, origin);
    getline(cin, cmp);
    if (origin.size() < cmp.size()) {
        cout << 0 << "\n";
        return 0;
    }
    int ans = 0;
    for (int k = 0; k <= origin.size() - cmp.size(); k++) {
        int temp = 0;
        for (int i = k; i <= origin.size() - cmp.size(); i++) {
            bool check = true;
            for (int j = 0; j < cmp.size(); j++) {
                if (origin[i + j] != cmp[j]) {
                    check = false;
                    break;
                }
            }
            if (check) {
                i += cmp.size() - 1;
                temp++;
                if (i > origin.size() - cmp.size())break;
            }
        }
        if (ans < temp)ans = temp;
    }
    cout << ans << "\n";
}

항상 방심하지 말자!!