結果

問題 No.430 文字列検索
ユーザー tkmst201tkmst201
提出日時 2017-05-14 21:24:18
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 190 ms / 2,000 ms
コード長 1,990 bytes
コンパイル時間 1,412 ms
コンパイル使用メモリ 165,148 KB
実行使用メモリ 27,028 KB
最終ジャッジ日時 2023-10-14 10:59:27
合計ジャッジ時間 3,115 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 190 ms
26,996 KB
testcase_02 AC 22 ms
4,412 KB
testcase_03 AC 22 ms
4,396 KB
testcase_04 AC 1 ms
4,348 KB
testcase_05 AC 1 ms
4,352 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 2 ms
4,352 KB
testcase_08 AC 188 ms
27,028 KB
testcase_09 AC 2 ms
4,352 KB
testcase_10 AC 14 ms
5,876 KB
testcase_11 AC 73 ms
7,856 KB
testcase_12 AC 73 ms
8,292 KB
testcase_13 AC 73 ms
8,112 KB
testcase_14 AC 60 ms
6,528 KB
testcase_15 AC 50 ms
5,524 KB
testcase_16 AC 26 ms
4,360 KB
testcase_17 AC 24 ms
4,456 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> P;

const ll INF = 1ll<<60;
const ll MOD = 1000000007;
const double EPS  = 1e-10;

struct RollingHash {
	vector<ll> mod;
	vector<vector<ll> > hs, pw;
	string s;
	ll base;
	int n;
	
	RollingHash() {}
	RollingHash(string s) { init(s); }
	
	void init(string _s) {
		s = _s;
		n = s.size();
		
		mod.clear();
		hs.clear();
		pw.clear();
		
		//mod.push_back(999999937);
		mod.push_back(1000000007);
		
		base = 9973;
		
		hs.resize(mod.size(), vector<ll>(n + 1));
		pw.resize(mod.size(), vector<ll>(n + 1));
		
		REP(i, mod.size()) {
			pw[i][0] = 1;
			REP(j, n) {
				hs[i][j + 1] = (hs[i][j] + s[j]) * base % mod[i];
				pw[i][j + 1] = pw[i][j] * base % mod[i];
			}
		}
	}
	
	inline ll hash(int l, int r, int i) {
		return (hs[i][r] - hs[i][l] * pw[i][r - l] % mod[i] + mod[i]) % mod[i];
	}
	
	inline bool match(int l1, int r1, int l2, int r2) {
		bool res = true;
		REP(i, mod.size()) if (hash(l1, r1, i) != hash(l2, r2, i)) res = false;
		return res;
	}
	
	int lcp(int i, int j) {
		int l = 0, r = min(n - i, n - j) + 1;
		while (r - l > 1) {
			int m = (l + r) / 2;
			if (match(i, i + m, j, j + m)) l = m;
			else r = m;
		}
		return l;
	}
};

int main() {
	string s;
	int m;
	
	cin >> s >> m;
	
	ll ans = 0;
	
	RollingHash rh(s);
	
	map<ll, int> ss[11];
	FOR(i, 1, 11) {
		REP(j, s.size()) {
			ss[i][rh.hash(j, j + i, 0)]++;
		}
	}
	
	REP(i, m) {
		string c;
		cin >> c;
		
		RollingHash tmp(c);
		ans += ss[c.size()][tmp.hash(0, c.size(), 0)];
	}
	
	cout << ans << endl;
	
	return 0;
}
0