#546600 (C++17) No.430 文字列検索

提出ソース

結果

問題	No.430 文字列検索
ユーザー	minato
提出日時	2020-09-04 06:19:42
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	72 ms / 2,000 ms
コード長	5,591 bytes
コンパイル時間	3,489 ms
コンパイル使用メモリ	244,148 KB
実行使用メモリ	20,064 KB
最終ジャッジ日時	2024-05-03 17:51:30
合計ジャッジ時間	4,820 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	72 ms 17,952 KB
testcase_02	AC	18 ms 12,080 KB
testcase_03	AC	19 ms 12,112 KB
testcase_04	AC	1 ms 6,940 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	1 ms 6,940 KB
testcase_08	AC	40 ms 17,340 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	5 ms 6,940 KB
testcase_11	AC	49 ms 19,992 KB
testcase_12	AC	58 ms 19,256 KB
testcase_13	AC	49 ms 19,436 KB
testcase_14	AC	46 ms 19,004 KB
testcase_15	AC	48 ms 20,064 KB
testcase_16	AC	36 ms 19,856 KB
testcase_17	AC	29 ms 19,408 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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
*/

yukicoder

結果

テストケース

ソースコード