文字列の操作いろいろ

Boyer-Moore法

void table(char *key) {
	int len = strlen(key);
	fill(skip, skip+CHAR_SET, len);

	for(int i = 0; i < len-1; i++) {
		skip[key[i]] = len-1-i;
	}

}

//位置取得。戻り値はインデックス
int search(char* text, char* key) {
	int textlen = strlen(text);
	int keylen = strlen(key);

	int ans = -1;
        //i++とすると、余分に１つすすむことになるので、やらない。
	for(int i = keylen-1; i < textlen;i++) {
		for(int j = 0; j <= keylen-1; j++) {
			//最後尾から先頭まで走査
			if(text[i-j] != key[keylen-1-j]) {
				i += skip[text[i-j]];
				break;
			}
			//見つかった
			ans = i-(keylen-1);
		}
		//見つかったら抜ける
		if(ans != -1) {
			break;
		}
	}
	return ans;

}

テーブルを作って、操作する。スキップできたり便利な半面、
textの文字数が少なかったりすると、時間が余計にかかりそう。