trieなるものを使えばいいらしい。
多分 O(20 * 150000) ぐらいかな〜
#include<cstdio> #include<vector> #include<algorithm> #include<string.h> #define rep(i,n) for(int i = 0; i < n; i++) #define rrep(i,o,n) for(int i = o; i <= n; i++) #define pb push_back using namespace std; int ch(char a){ switch(a){ case 'A': return 0; case 'T': return 1; case 'G': return 2; case 'C': return 3; } return -1; } int main(){ int n, g, b, ans = 0, l, maxl, vlen; char w[150001], v[21]; vector<int> t[5]; scanf("%d%s",&n,w); int wlen = strlen(w); rep(i,5) t[i].pb(0); rep(i,n){ scanf("%s",v); g = 0; vlen = strlen(v); rep(j,vlen){ b = ch(v[j]); if(!t[b][g]){ t[b][g] = t[0].size(); rep(i,5) t[i].pb(0); } g = t[b][g]; } t[4][g] = 1; } int i = 0; while(i < wlen-1){ maxl = 0; rrep(j,max(0,i-19),i){ l = j; g = 0; while(l < wlen && t[ch(w[l])][g]){ g = t[ch(w[l])][g]; if(t[4][g]) maxl = max(maxl, l); l++; } } i = maxl; ans++; } printf("%d\n",ans); return 0; }
strlen(w) を wlen に訂正。。。
strlen は O(N) だってことを知らなかった・・・
string の .size() は O(1) だよね? string 最高!