結果

問題 No.430 文字列検索
ユーザー kotatsugamekotatsugame
提出日時 2019-10-15 07:10:37
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 11 ms / 2,000 ms
コード長 2,881 bytes
コンパイル時間 780 ms
コンパイル使用メモリ 81,164 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-10 00:36:15
合計ジャッジ時間 1,486 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 10 ms
5,248 KB
testcase_02 AC 8 ms
5,248 KB
testcase_03 AC 8 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 1 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 6 ms
5,248 KB
testcase_09 AC 1 ms
5,248 KB
testcase_10 AC 3 ms
5,248 KB
testcase_11 AC 10 ms
5,248 KB
testcase_12 AC 11 ms
5,248 KB
testcase_13 AC 11 ms
5,248 KB
testcase_14 AC 10 ms
5,248 KB
testcase_15 AC 9 ms
5,248 KB
testcase_16 AC 7 ms
5,248 KB
testcase_17 AC 7 ms
5,248 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:135:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  135 | main()
      | ^~~~

ソースコード

diff # 

#include<iostream>
using namespace std;
//construct SA by SA-IS O(N)
#include<string>
#include<vector>
struct SA{
	string s;
	vector<int>sa;
	SA(const string&s_):s(s_)
	{
		sa=build(vector<int>(s.begin(),s.end()),256);
	}
	vector<int>induced_sort(const vector<int>&S,const vector<int>&id,const vector<bool>&SL,vector<int>last)
	{
		vector<int>first(last);
		vector<int>ret(id.size());
		ret[0]=id[0];
		for(int i=0;i<id.size();i++)
		{
			if(id[i]>=1&&!SL[id[i]-1])
			{
				ret[first[S[id[i]-1]-1]++]=id[i]-1;
			}
			else if(ret[i]>=1&&!SL[ret[i]-1])
			{
				ret[first[S[ret[i]-1]-1]++]=ret[i]-1;
			}
		}
		for(int i=id.size();i--;)
		{
			if(ret[i]>=1&&SL[ret[i]-1])
			{
				ret[--last[S[ret[i]-1]]]=ret[i]-1;
			}
		}
		return ret;
	}
	vector<int>build(vector<int>S,int maxval)
	{
		if(S.size()<=1)
		{
			return S.empty()?(vector<int>){0}:(vector<int>){1,0};
		}
		S.push_back(0);
		vector<int>cnt(maxval,0);
		vector<bool>SL(S.size());//S=>true,L=>false
		for(int i=S.size();i--;)
		{
			cnt[S[i]]+=1;
			SL[i]=i+1==S.size()||S[i]<S[i+1]||S[i]==S[i+1]&&SL[i+1];
		}
		for(int i=1;i<maxval;i++)cnt[i]+=cnt[i-1];
		vector<int>last(cnt);
		vector<int>id(S.size());
		vector<int>is_LMS(S.size());
		int LMScnt=0;
		for(int i=1;i<S.size();i++)
		{
			if(!SL[i-1]&&SL[i])
			{
				is_LMS[i]=1;
				id[--cnt[S[i]]]=i;
				LMScnt+=1;
			}
		}
		id=induced_sort(S,id,SL,last);
		int LMSsub=1;
		int pre=-1;
		is_LMS[id[0]]=LMSsub++;
		for(int i=1;i<id.size();i++)
		{
			if(is_LMS[id[i]])
			{
				if(pre>=0&&S[pre]==S[id[i]])
				{
					int k;
					for(k=1;S[pre+k]==S[id[i]+k]&&!is_LMS[pre+k]&&!is_LMS[id[i]+k];k++);
					LMSsub-=S[pre+k]==S[id[i]+k]&&is_LMS[pre+k]&&is_LMS[id[i]+k];
				}
				pre=id[i];
				is_LMS[id[i]]=LMSsub++;
			}
		}
		vector<int>newstr(LMScnt);
		vector<int>rev(LMScnt);
		int counter=0;
		for(int i=0;i<S.size();i++)
		{
			if(is_LMS[i])
			{
				newstr[counter]=is_LMS[i];
				rev[counter]=i;
				counter+=1;
			}
		}
		vector<int>sortedLMS=build(newstr,LMSsub);
		id.assign(S.size(),0);
		for(int i=1;i<sortedLMS.size();i++)
		{
			int I=rev[sortedLMS[i]];
			id[cnt[S[I]]++]=I;
		}
		return induced_sort(S,id,SL,last);
	}
	int operator[](int i)const{return sa[i];}
	int lower_bound(const string&t)const
	{
		int L=-1,R=sa.size();
		while(R-L>1)
		{
			int M=L+R>>1;
			if(s.compare(sa[M],t.size(),t)>=0)R=M;
			else L=M;
		}
		return R;
	}
	int upper_bound(const string&t)const
	{
		int L=-1,R=sa.size();
		while(R-L>1)
		{
			int M=L+R>>1;
			if(s.compare(sa[M],t.size(),t)<=0)L=M;
			else R=M;
		}
		return R;
	}
	bool contain(const string&t)const
	{
		int id=lower_bound(t);
		return id<sa.size()&&s.compare(sa[id],t.size(),t)==0;
	}
	int size()const{return sa.size();}
};
main()
{
	string s;cin>>s;
	SA P(s);
	int N;cin>>N;
	int ans=0;
	for(int i=0;i<N;i++)
	{
		string t;cin>>t;
		ans+=P.upper_bound(t)-P.lower_bound(t);
	}
	cout<<ans<<endl;
}
0