백준 1786 찾기 쉬운 풀이(C++/CPP)

문제링크 : https://www.acmicpc.net/problem/1786

문제 접근

• KMP, Rabin-Karp 기본문제
• 개념 참조 : https://dev-jango.tistory.com/20

시간복잡도 계산

• KMP, Rabin-Karp : O(M+N)
  • M : 첫번째 문자열 길이
  • N : 두번쨰 문자열 길이

인트 계산

• 최대 숫자 : 최대 문자열 길이 : 1e6

코드(KMP 풀이)

#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
vector<int> fail(string& s) {
    vector<int> f(s.size());
    int j=0;
    for(int i=1; i<s.size(); i++) {
        while(j>0 && s[j] != s[i]) j = f[j-1];
        if(s[i] == s[j]) f[i] = ++j;
    }
    return f;
}
 
int main() {
    string T,P; getline(cin, T); getline(cin, P);
    
    vector<int> f = fail(P);
    
    int j=0;
    vector<int> rs;
    for(int i=0; i<T.size(); i++) {
        while(j>0 && T[i] != P[j]) j = f[j-1];
        if(T[i] == P[j]) j++;
        if(j==P.size()) {
            rs.push_back(i+2-P.size());
            j = f[j-1];
        }
    }
    
    cout << rs.size() << '\n';
    for(int x : rs) cout << x << '\n';
    return 0;
}
 
 

코드(Rabin Karp 풀이)

#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
typedef long long ll;
 
ll a = 302;
ll p = 1e9+7;
ll powa[1000010];
 
int main() {
    string T,P; getline(cin, T); getline(cin, P);
    
    int lenT = T.size();
    int lenP = P.size();
    if(lenT < lenP) {
        cout << 0 << '\n';
        return 0;
    }
    
    
    // a의 제곱값을 미리 구해놓음
    powa[0] = 1;
    for(int i=1; i<P.size(); i++) {
        powa[i] = powa[i-1] * a %p;
    }
    
    // 각각 P길이만큼 해시값 구함
    ll hashT = 0;
    ll hashP = 0;
    
    for(int i=0; i<P.size(); i++) {
        hashT = (hashT + T[i] * powa[P.size()-1-i]) %p;
        hashP = (hashP + P[i] * powa[P.size()-1-i]) %p;
    }
    
    vector<int> rs;
    if(hashT == hashP) rs.push_back(1);
    
    for(int i=1; i<=(T.size()-P.size()); i++) {
        // 앞글자 빼고, a만큼 곱해서 한자리씩 올리고, 새로 한글자 추가
        hashT = (hashT - T[i-1] * powa[P.size()-1])%p;
        // 음수인경우 확인
        if(hashT < 0) hashT += p;
        hashT = hashT * a % p;
        hashT = (hashT + T[i+P.size()-1] ) % p;
        if(hashT == hashP) rs.push_back(i+1);
        
    }
    
    cout << rs.size() << '\n';
    for(int x : rs) cout << x << '\n';
    
    return 0;
}
 
 

문제유형

• KMP
• Rabin Karp