結果

問題 No.430 文字列検索
コンテスト
ユーザー srup٩(๑`н´๑)۶
提出日時 2016-10-18 18:54:50
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 438 ms / 2,000 ms
コード長 816 bytes
コンパイル時間 446 ms
コンパイル使用メモリ 63,324 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-10 00:10:57
合計ジャッジ時間 5,352 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;
const ll mod = 1e9 + 7;

string moto;
int containt(string a){
	int ret = 0;
	if(a.size() > moto.size()) return ret;
	ll t = 1;
	rep(i, a.size()){
		t *= mod;
	}
	ll hasha = 0, hashmoto = 0;
	rep(i, a.size()){
		hasha = hasha * mod + a[i];
		hashmoto = hashmoto * mod + moto[i];
	}

	for (int i = 0; i + a.size() <= moto.size(); ++i){
		if(hasha == hashmoto) ret++;
		hashmoto= hashmoto * mod + moto[i + a.size()] - moto[i] * t;
	}
	return ret;
}

int main(void){
	cin >> moto;
	int n; cin >> n;
	int ans = 0;
	rep(i, n){
		string s; cin >> s;
		ans += containt(s);
	}
	printf("%d\n", ans);
	return 0;
}
0