結果

問題 No.430 文字列検索
ユーザー tkmst201tkmst201
提出日時 2017-05-14 20:54:47
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 41 ms / 2,000 ms
コード長 2,575 bytes
コンパイル時間 2,309 ms
コンパイル使用メモリ 153,712 KB
実行使用メモリ 4,356 KB
最終ジャッジ日時 2023-10-14 10:59:23
合計ジャッジ時間 3,078 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,352 KB
testcase_01 AC 35 ms
4,352 KB
testcase_02 AC 41 ms
4,348 KB
testcase_03 AC 40 ms
4,352 KB
testcase_04 AC 2 ms
4,352 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
4,352 KB
testcase_07 AC 2 ms
4,356 KB
testcase_08 AC 32 ms
4,352 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 3 ms
4,348 KB
testcase_11 AC 38 ms
4,352 KB
testcase_12 AC 37 ms
4,348 KB
testcase_13 AC 38 ms
4,348 KB
testcase_14 AC 38 ms
4,352 KB
testcase_15 AC 37 ms
4,352 KB
testcase_16 AC 37 ms
4,348 KB
testcase_17 AC 38 ms
4,348 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 SuffixArray {
	string s; // 接頭辞配列を作る文字列
	vector<int> rank; // 各サフィックスの辞書順ランク
	vector<int> sa; // 各サフィックスの先頭位置
	int w; // 現在見ている文字列幅
	
	// 2つのサフィックスの比較
	bool comp(int i, int j) {
		if (rank[i] != rank[j]) return rank[i] < rank[j];
		
		int l = i + w <= s.size() ? rank[i + w] : -1;
		int r = j + w <= s.size() ? rank[j + w] : -1;

		return l < r;
	}
	
	SuffixArray() {}
	SuffixArray(string s) { init(s); }
	
	// 接頭辞配列の構築
	void init(string _s) {
		s = _s;
		
		rank.clear(); rank.resize(s.size() + 1);
		sa.clear(); sa.resize(s.size() + 1);
		
		REP(i, s.size() + 1) {
			rank[i] = i < s.size() ? s[i] : -1;
			sa[i] = i;
		}
		
		for (w = 1; w <= s.size(); w *= 2) {
			// ランクで配列saをソート
			sort(ALL(sa), [&](const int& i, const int& j) { return comp(i, j); });
			
			vector<int> tmp(s.size() + 1);
			tmp[ sa[0] ] = 0;
			FOR(i, 1, s.size() + 1) tmp[ sa[i] ] = tmp[ sa[i - 1] ] + comp(sa[i - 1], sa[i]);
			
			copy(ALL(tmp), rank.begin());
		}
	}
	
	// 文字列strとSのサフィックスが一致する配列saのインデックスを返す
	int query(string str) {
		int l = 0, r = s.size();
		while (r - l > 1) {
			int m = (l + r) / 2;
			
			if (s.compare(sa[m], str.size(), str) < 0) l = m;
			else r = m;
		}
		
		if (s.compare(sa[r], str.size(), str) != 0) return -1;
		return r;
	}
	
	// 文字列Sの部分文字列から文字列strと一致する個数を数える
	int count(string str) {
		int idx = query(str);
		if (idx == -1) return 0;
		
		int l = idx, r = s.size() + 1;
		
		while (r - l > 1) {
			int m = (r + l) / 2;
			
			if (s.compare(sa[m], str.size(), str) > 0) r = m;
			else l = m;
		}
		
		return l - idx + 1;
	}
};

int main() {
	string s;
	int m;
	
	cin >> s >> m;
	
	ll ans = 0;
	
	SuffixArray sa(s);
	REP(i, m) {
		string c;
		cin >> c;
		ans += sa.count(c);
	}
	
	cout << ans << endl;
	
	return 0;
}
0