제출 #48982

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48982		Namnamseo	Selling RNA Strands (JOI16_selling_rna)	C++17	60 / 100	1572 ms	217008 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
#define sz(v) ((v).size())
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define coord_comp(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define v_index(v, x) (lower_bound(all(v),x)-(v).begin())
typedef pair<int,int> pp;
typedef long long ll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T1,typename T2>
void read(pair<T1,T2>& p){ read(p.first); read(p.second); }
template<typename T,typename... Args>
void read(T&a,Args&...b){ read(a); read(b...); }

inline int conv(char x){
	if(x=='A') return 0;
	if(x=='U') return 1;
	if(x=='G') return 2;
	if(x=='C') return 3;
	return 4;
}

struct node {
	node *p[5];
	node *fail;
	vector<int> term;
	node(){
		for(int i=0; i<5; ++i) p[i]=0;
		fail=0;
	}
	void put(int ind,char* cp){
		if((*cp) == 0){
			term.pb(ind);
			return;
		}
		int x=conv(*cp);
		if(!p[x]) p[x]=new node();
		p[x]->put(ind, cp+1);
	}
} *root;

int n,m;

string hay[100010];
string needle[100010][2];

void in(){
	read(n,m);
	char buf[200010];
	for(int i=1; i<=n; ++i){
		scanf("%s",buf); hay[i]=string(buf);
	}
	root = new node();
	for(int i=1; i<=m; ++i){
		scanf("%s",buf); needle[i][0]=string(buf);
		scanf("%s",buf); needle[i][1]=string(buf);
		int p=needle[i][0].length();
		int q=needle[i][1].length();
		for(int j=0; j<q; ++j) buf[j]=needle[i][1][j];
		buf[q] = '$';
		for(int j=0; j<p; ++j)
			buf[q+1+j]=needle[i][0][j];
		buf[p+q+1]=0;
		root->put(i, buf);
	}
}

void aho(){
	queue<node*> q;
	root->fail = root;
	for(int i=0; i<5; ++i){
		if(root->p[i]){
			root->p[i]->fail = root;
			q.push(root->p[i]);
		} else {
			root->p[i]=root;
		}
	}
	while(q.size()){
		node *m=q.front(); q.pop();
		for(int i=0;i<5;++i){
			auto n=m->p[i];
			if(n){
				auto tmp=m->fail;
				while(tmp!=root && !tmp->p[i]) tmp=tmp->fail;
				if(tmp->p[i]) tmp=tmp->p[i];
				n->fail = tmp;
				for(int t:tmp->term)
					n->term.pb(t);
				q.push(n);
			} else {
				auto tmp=m->fail;
				while(tmp!=root && !tmp->p[i]) tmp=tmp->fail;
				if(tmp->p[i]) tmp=tmp->p[i];
				m->p[i]=tmp;
			}
		}
	}
}

int ans[100010];

int main(){
	in();
	aho();
	for(int i=1; i<=n; ++i){
		string a=hay[i]+string("$")+hay[i];
		node *cur=root;
		for(char c : a){
			int x=conv(c);
			cur=cur->p[x];
			for(int t:cur->term) ++ans[t];
		}
	}
	for(int i=1; i<=m; ++i) printf("%d\n",ans[i]);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

selling_rna.cpp: In function 'void read(int&)':
selling_rna.cpp:10:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(int& x){ scanf("%d",&x); }
                    ~~~~~^~~~~~~~~
selling_rna.cpp: In function 'void read(ll&)':
selling_rna.cpp:11:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(ll& x){ scanf("%lld",&x); }
                   ~~~~~^~~~~~~~~~~
selling_rna.cpp: In function 'void in()':
selling_rna.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",buf); hay[i]=string(buf);
   ~~~~~^~~~~~~~~~
selling_rna.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",buf); needle[i][0]=string(buf);
   ~~~~~^~~~~~~~~~
selling_rna.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",buf); needle[i][1]=string(buf);
   ~~~~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 0 / 40