#121420 (C++14) No.430 文字列検索

• 問題: No.430 文字列検索
• ユーザー: ciel
• 提出日時: 2016-10-03 22:47:08
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 41 ms / 2,000 ms
• コード長: 1,544 bytes
• コンパイル時間: 1,182 ms
• コンパイル使用メモリ: 83,008 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-05-03 04:30:55
• 合計ジャッジ時間: 2,347 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	25 ms; 5,376 KB
testcase_02	AC	41 ms; 5,376 KB
testcase_03	AC	35 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	21 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	3 ms; 5,376 KB
testcase_11	AC	34 ms; 5,376 KB
testcase_12	AC	34 ms; 5,376 KB
testcase_13	AC	34 ms; 5,376 KB
testcase_14	AC	32 ms; 5,376 KB
testcase_15	AC	32 ms; 5,376 KB
testcase_16	AC	29 ms; 5,376 KB
testcase_17	AC	35 ms; 5,376 KB

ソースコード

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
struct SAComp{
	const int h,*g;
	SAComp(const int h, const int* g) : h(h), g(g) {}
	bool operator()(const int a, const int b){
		return a == b ? false : g[a] != g[b] ? g[a] < g[b] : g[a+h] < g[b+h];
	}
};
vector<int> buildSA(const string &t){
	int n=t.size();
	int g[n],b[n];
	vector<int>suff(n);
	for(int i=0;i<n;i++)suff[i]=i,g[i]=t[i];
	b[0]=b[n-1]=0;
	sort(suff.begin(),suff.end(),SAComp(0,g));
	for(int h=1;b[n-1]!=n-1;h<<=1){
		SAComp comp(h,g);
		sort(suff.begin(),suff.end(),comp);
		for(int i=0;i<n-1;i++)b[i+1]=b[i]+comp(suff[i],suff[i+1]);
		for(int i=0;i<n;i++)g[suff[i]]=b[i];
	}
	return suff;
}
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	string s;
	cin>>s;
	s+='$';
	int n=s.size();
	vector<int>suff=buildSA(s);
	vector<pair<char,int>>sorted(n);
	for(int i=0;i<n;i++)sorted[i]={s[(suff[i]-1+n)%n],i};
	sort(sorted.begin(),sorted.end());

	int R=0;
	int T;
	for(cin>>T;T--;){
		string q;
		cin>>q;
		int start=0,stop=n,idx=q.size()-1;
		for(;idx>=0;idx--){
			pair<char,int> ql={q[idx],start},qr={q[idx],stop};
			start=lower_bound(sorted.begin(),sorted.end(),ql)-sorted.begin();
			stop=lower_bound(sorted.begin(),sorted.end(),qr)-sorted.begin();
			if(start==stop)break;
		}
		if(idx<0){
			R+=stop-start;
			//{vector<int>v;for(;start<stop;start++)v.push_back(suff[start]);sort(v.begin(),v.end());for(auto &e:v)printf("%d\n",e);}
			//puts("1");
		}else{
			//puts("0");
		}
	}
	printf("%d\n",R);
}