[백준] #16916 부분 문자열

문제
시간초과가 계속 났다~~~ 내생각엔 Hash배열에 미리 저장해두고 그걸 참조하는게 오래 걸리는 것 같다.

#include<iostream>
#include<string>
#include<climits>

using namespace std;
long long Hash[1000000];

int x=27;
long long pHash=0;
long long mult=1,mult2=1,mult3=1;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long num,num1;
    
    
    string s,p;
    cin>>s>>p;
    if(s==p){
        cout<<1;
        return 0;
    }
    if(s.length()<p.length()){
        cout<<0;
        return 0;
    }
   
   for(int i=0;i<s.length();i++){
       Hash[i]=(s[i]-96)*mult;
       mult=mult*x;
   }
   

   for(int i=0;i<p.length();i++){
       pHash+=(p[i]-96)*mult2;
       mult2=mult2*x;
   }    

   for(int i=0;i<s.length()-p.length();i++){
        num=0;
        num1=pHash;
        
        for(int j=i;j<p.length()+i;j++){
            num+=Hash[j];
        }

        num1*=mult3;

        if(num==num1){
            cout<<1;
            return 0;
        }
        mult3*=x;
    }
    cout<<0;
    return 0;


}

그래서 다른 분의 코드를 보고 KMP 알고리즘으로 푸는 식으로 수정했다.

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int N;

vector<int> func(string P){
    
    vector<int> V(P.length(), 0);
    int j = 0;
    for(int i = 1; i<P.length(); i++){
        while(j>0 && P[i]!=P[j]){
            j = V[j-1];
        }
        if(P[i] == P[j]){
            V[i] = ++j;
        }
    }
    return V;
}

int KMP(string S, string P){
    vector<int> V = func(P);
    int j = 0;
    
    for(int i = 0; i<S.length(); i++){      
        while(j>0 && S[i] != P[j]){
            j = V[j-1];
        }
        if(S[i] == P[j]){
            if(j== P.length()-1) 
                return 1;      
            else j+=1;
        }
    }
    return 0;
    
}

int main(){
    
    string S, P;
    cin >> S >> P;
 
    N = (int)S.length();
    
    cout << KMP(S, P);

    return 0;
}

kmp 알고리즘 관련
https://blog.naver.com/ndb796/221240660061