結果

問題 No.430 文字列検索
ユーザー minatominato
提出日時 2020-09-04 06:19:42
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 67 ms / 2,000 ms
コード長 5,591 bytes
コンパイル時間 3,273 ms
コンパイル使用メモリ 244,216 KB
実行使用メモリ 19,072 KB
最終ジャッジ日時 2024-11-10 00:46:26
合計ジャッジ時間 4,307 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 67 ms
16,784 KB
testcase_02 AC 17 ms
11,940 KB
testcase_03 AC 16 ms
11,808 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 42 ms
16,912 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 5 ms
5,248 KB
testcase_11 AC 52 ms
18,980 KB
testcase_12 AC 56 ms
19,072 KB
testcase_13 AC 53 ms
18,852 KB
testcase_14 AC 48 ms
18,984 KB
testcase_15 AC 46 ms
18,972 KB
testcase_16 AC 34 ms
18,764 KB
testcase_17 AC 30 ms
18,696 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("avx2,avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
constexpr char ln = '\n';
template<class T1, class T2> inline bool chmax(T1 &a, T2 b) {if (a < b) {a = b; return true;} return false;}
template<class T1, class T2> inline bool chmin(T1 &a, T2 b) {if (a > b) {a = b; return true;} return false;}
struct Fast_ios {Fast_ios() {cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20);};} fast_ios;
/////////////////////////////////////////////////////////////////////////////////////////////


template<class C>
struct SuffixAutomaton {
    //各nodeは複数の部分文字列を担当する
    //最長の文字列の長さはnode.len
    //最短の文字列の長さはnode.link.len+1
	struct State {
		int len, link, original;
		map<C, int> nex;
		State(int len, int link, int original) : len(len), link(link), original(original) {}
	};
	vector<State> node;
    vector<int> tid;
	int last;
 
	SuffixAutomaton() : last(0) {node.emplace_back(0,-1,0);}
 
    //文字をcurの直後に追加する
    //各文字に紐づいた値でdpしたいときはdp[last] += val する
	int add(C c, int cur = -1) {
		if (cur == -1) cur = last;
 
		if (node[cur].nex.count(c) && node[node[cur].nex[c]].len == node[cur].len + 1) {
			int q = node[cur].nex[c];
			return last = q;
		}

        int p = cur;
		int nex = node.size();
		node.emplace_back(node[p].len+1,0,nex);
		while (p != -1 && !node[p].nex.count(c)) {
			node[p].nex[c] = nex;
			p = node[p].link;
		}
		if (p == -1) {
            node[nex].link = 0;
			return last = nex;
		}
 
		int q = node[p].nex[c];
		if (node[p].len+1 == node[q].len) {
			node[nex].link = q;	
		} else {
			int clone = node.size();
			node.emplace_back(node[q]);
			node[clone].len = node[p].len + 1;
 
			while (p != -1 && node[p].nex[c] == q) {
				node[p].nex[c] = clone;
				p = node[p].link;
			}
            node[q].link = node[nex].link = clone;
		}
		return last = nex;
	}
 	
	void sortTopologically() {
		vector<int> deg(node.size());

		for(int i=0; i < (int)node.size(); i++) {
			for(auto &p : node[i].nex) deg[p.second]++;
		}
		queue<int> que;
		que.emplace(0);
		while(!que.empty()) {
			int v = que.front();
			que.pop();
			tid.emplace_back(v);
			for(auto &p : node[v].nex) {
				if(--deg[p.second] == 0) que.emplace(p.second);
			}
		}
	}
 
	vector<int> buildSuffixTree() {
		vector<int> ret;
 
		vector<vector<int>> G(node.size());
		for(int i = 1; i < (int)node.size(); i++) G[node[i].link].emplace_back(i);
		queue<int> que;
		que.emplace(0);
		while(!que.empty()) {
			int v = que.front();
			que.pop();
			ret.emplace_back(v);
			for(auto nv : G[v]) que.push(nv);
		}
		return ret;
	}

	//相異なる部分文字列の個数
    long long numberOfDistinctSubstrings() {
        assert(!tid.empty());
        vector<long long> dp(node.size());
        dp[0] = 1;
        long long ret = 0;
        for (int i = 0; i < (int)node.size(); ++i) {
            int u = tid[i];
            ret += dp[u];
            for (auto &j : node[u].nex) {
                dp[j.second] += dp[u];
            }
        }

        return ret-1;
    }

    //SAにある部分文字列が何回出現するか調べられるdpテーブルを返す
    //根から辿った先の添え字の値が出現する回数
    vector<long long> enumNumberOfOccurrences() {
        auto vid = buildSuffixTree();
        vector<long long> dp(node.size());
        for (int i = (int)node.size()-1; i > 0; --i) {
            int u = vid[i];
            if (node[u].original==u) dp[u]++;
            dp[node[u].link] += dp[u];
        }
        return dp;
    }

	//部分文字列の初回出現位置 [l,r)のrを返す
	vector<int> enumFirstOccurences() {
		assert(!tid.empty());
		vector<int> ret(node.size());
        for (int i = (int)node.size()-1; i >= 0; --i) {
            ret[tid[i]] = node[node[tid[i]].original].len;
        }

        return ret;
	}

	//部分文字列の最終出現位置 [l,r)のrを返す
    vector<int> enumLastOccurrences() {
        assert(!tid.empty());
        vector<int> ret(node.size());
        for (int i = (int)node.size()-1; i >= 0; --i) {
            int u = tid[i];
            ret[u] = max(ret[u],node[u].len);
            if (i > 0) ret[node[u].link] = max(ret[node[u].link],ret[u]);
        }

        return ret;
    }

    State operator[](int i) const {return node[i];}
};

////////////////////////////////////////////////////////////////////////////////////

void yosupo_judge() {
	string S; cin >> S;
	SuffixAutomaton<char> SA;
	for (int i = 0, cur = -1; i < SZ(S); i++) {
		cur = SA.add(S[i],cur);
	}
	SA.sortTopologically();
	cout << SA.numberOfDistinctSubstrings() << ln;
}

void yuki430() {
	string S; cin >> S;
	SuffixAutomaton<char> SA;
	for (int i = 0, cur = 0; i < SZ(S); i++) {
		cur = SA.add(S[i],cur);
	}

	int Q; cin >> Q;
	auto dp = SA.enumNumberOfOccurrences();
	ll ans = 0;
	while (Q--) {
		string T; cin >> T;
		int cur = 0;
		for (int i = 0; i < SZ(T); i++) {
			if (!SA[cur].nex.count(T[i])) {
				cur = -1;
				break;
			}
			cur = SA[cur].nex[T[i]];
		}
		if (~cur) ans += dp[cur];
	}

	cout << ans << ln;
}

int main() {
	//yosupo_judge();
	yuki430();
}

/*
  verified on 2020/09/03
  https://judge.yosupo.jp/problem/number_of_substrings
*/
0