ローリングハッシュ で DNA synthesizer(JOI 2010 春合宿)

gistfile1.cpp

#include <cstring>
#include <climits>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef unsigned long long ull;

const ull B=10000007;
const int INF=INT_MAX/2;
int mins[150000];
ull sohas[50000];
char want[150002],ins[22];
int main(){
    int N;
    scanf("%d\n%s\n",&N,want);
    for(int i=0;i<N;i++){
        scanf("%s\n",ins);
        int si=strlen(ins);
        ull ha=0;
        for(int j=0;j<si;j++){
            ha=ha*B+ins[j];
        }
        sohas[i]=ha;
    }
    sort(sohas,sohas+N);
    int wsi=strlen(want);
    for(int i=0;i<wsi;i++){
        mins[i]=INF;
    }
    ull wha=0;
    for(int i=0;i<wsi;i++){
        wha=wha*B+want[i];
        if(binary_search(sohas,sohas+N,wha)) mins[i]=1;
        ull befha=want[i],bb=1;
        int mback=0;
        for(int j=1;j<=min(19,i);j++){
            bb*=B;
            befha+=want[i-j]*bb;
            if(binary_search(sohas,sohas+N,befha)) mback=j;
        }
        for(int j=i-mback;j<i;j++){
            mins[i]=min(mins[j]+1,mins[i]);
        }
    }
    printf("%d\n",mins[wsi-1]);
}