CSES - HIIT Open 2016 - Results
Submission details
Task:DNA sequence
Sender:Game of Nolife
Submission time:2016-05-28 11:22:16 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.17 sdetails

Code

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

struct SuffixAutomaton{
	vector<map<char, int> > g;
	vector<int> link;
	vector<int> len;
	int last;
	void addC(char c){
		int p=last;
		int t=link.size();
		link.push_back(0);
		len.push_back(len[last]+1);
		g.push_back(map<char, int>());
		while (p!=-1&&g[p].count(c)==0){
			g[p][c]=t;
			p=link[p];
		}
		if (p!=-1){
			int q=g[p][c];
			if (len[p]+1==len[q]){
				link[t]=q;
			}
			else{
				int qq=link.size();
				link.push_back(link[q]);
				len.push_back(len[p]+1);
				g.push_back(g[q]);
				while (p!=-1&&g[p][c]==q){
					g[p][c]=qq;
					p=link[p];
				}
				link[q]=qq;
				link[t]=qq;
			}
		}
		last=t;
	}
	SuffixAutomaton(string s){
		last=0;
		g.push_back(map<char, int>());
		link.push_back(-1);
		len.push_back(0);
		for (int i=0;i<(int)s.size();i++){
			addC(s[i]);
		}
	}
};

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin>>s;
	SuffixAutomaton sa(s);
	int n;
	cin>>n;
	for (int i=0;i<n;i++){
		string t;
		cin>>t;
		int a=0;
		int f=0;
		for (int j=0;j<(int)t.size();j++){
			if (sa.g[a][t[j]]==0){
				f=1;
				break;
			}
			else{
				a=sa.g[a][t[j]];
			}
		}
		if (f==1){
			cout<<"NO\n";
		}
		else{
			cout<<"YES\n";
		}
	}
}

Test details

Test 1

Verdict: ACCEPTED

input
ACGCGGGCTCCTAGCGTTAGCAGTTGAGTG...

correct output
YES
YES
NO
NO
YES
...

user output
YES
YES
NO
NO
YES
...