JOI 2010 春合宿 day2-2 「DNA synthesizer」

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 最高！