Submission #921306

---

Source Code Expand

#include <bits/stdc++.h>
#define FOR(i,a,b) for(ut i=(a);i<(ut)(b);i++)
#define REP(i,b) FOR(i,0,b)
#define ALL(c) c.begin(),c.end()
#define PB push_back
#define cat //cout << __LINE__ << endl;
using namespace std;
typedef long long LL;
typedef double ld;
typedef int ut;
typedef complex<int> cli;
typedef vector<ut> VI;
typedef pair<ut,ut> pr;
typedef pair<ut,pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef priority_queue<pr,Vpr> PQ;
const int SIZE=5+1e5;
const int alpha='z'-'a'+1;
int nums[SIZE][alpha][alpha];
int smaller[SIZE];
string s[SIZE];
struct Trie{
	Trie* next[alpha];
	bool isEnd;
	int size,tall;
	void init(){
		size=0;
		isEnd=false;
	}
	Trie():tall(0){init();}
	Trie(int x):tall(x){init();}
	Trie* nextNode(int target,bool unmake=false);
	Trie* nextNode(string &s,bool unmake=false){
		if(s.size()==tall) return NULL;
		return nextNode(s[tall]-'a',unmake);
	}
};
Trie root;
Trie nodes[SIZE*10];
int nextnodes=1;
Trie* Trie::nextNode(int target,bool unmake){

		if(!next[target]){
			if(unmake) return &nodes[0];
			next[target] = &nodes[nextnodes++];
			next[target]->tall=tall+1;	
		} 
		return next[target];
}
bool find(string &s,Trie* now){		
	while(now->nextNode(s)){
		now=now->nextNode(s);	
	}
	return now->isEnd;	
}
void add(string &s,Trie* root){
	Trie* now=root;
	while(now->nextNode(s)){
		now->size++;
		now=now->nextNode(s);	
	}
	now->isEnd=true;
	now->size++;
}
void analys(int x){
	Trie* now= &root;
	REP(i,s[x].size()){
		if(now->isEnd) smaller[x]++;
		FOR(j,'a','z'+1){
			if(s[x][i]==j) continue;
			nums[x][j-'a'][s[x][i]-'a']+=now->nextNode(j-'a',true)->size;
		}
		now=now->nextNode(s[x],true);
	}
}
bool isFaster(string &p,char a,char b){
	REP(i,p.size()){
		if(p[i]==a) return true;
		if(p[i]==b) return false;
	}
}
int solve(int x,string p){
	int ans=0;
	REP(i,alpha) REP(j,i){
		ans+=nums[x][p[j]-'a'][p[i]-'a'];
		//if(nums[x][i][j])cout << x <<" " <<  char(i+'a') <<" " << char(j+'a') << " " << nums[x][i][j] << endl; 
	}
	return ans+smaller[x];
}
int main(){
	int N;
	cin.tie(0);
	cin >> N;
	REP(i,SIZE*10) nodes[i].init();
	REP(i,N){
		cin >> s[i];
		add(s[i], &root);
	}
	REP(i,N){
		analys(i);
	}
	int Q,k;
	cin >> Q;
	string p;
	REP(i,Q){
		cin >> k >> p;
		cout << solve(k-1,p)+1 << endl;
	}
	return 0;
}

Submission Info

Judge Result