結果

問題 No.430 文字列検索
コンテスト
ユーザー tkmst201
提出日時 2017-05-14 20:54:47
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 38 ms / 2,000 ms
コード長 2,575 bytes
コンパイル時間 1,482 ms
コンパイル使用メモリ 166,772 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-10 00:15:07
合計ジャッジ時間 2,482 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

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