Submission #921101

---

Source Code Expand

#include<iostream>
#include<map>
using namespace std;
const int NQmax = 100000;
int N,Q;
string S[NQmax];
int prefix[NQmax];
map<int, int> former[NQmax];

struct trie {
  int k; // index of this node
  int n; // number of children
  struct trie* c[26];
} root[400000];

int main(){
  cin >> N;
  for(int i=0; i<N; i++){
    cin >> S[i];
  }
  int n = 1;
  for(int i=0; i<N; i++){
    struct trie *t = root;
    for(int j=0; j<S[i].size(); j++){
      int c = S[i][j]-'a';
      if(t->c[c] == NULL) t->c[c] = root+n;
      n++;
      t->c[c]->n++;
      t=t->c[c];
    }
    t->k=i+1;
  }

  for(int i=0; i<N; i++){
    struct trie *t=root;
    for(int j=0; j<S[i].size(); j++){
      int c = S[i][j]-'a';
      struct trie* s = t->c[c];
      if(t->k > 0) prefix[i]++;
      for(int k=0; k<26; k++){
        if(k==c|| t->c[k]==NULL) continue;
        former[i][k*26+c] += t->c[k]->n;
      }
      t=s;
    }
  }

  cin >> Q;
  for(int i=0; i<Q; i++){
    int K;
    string P;
    cin >> K;
    cin >> P;
    int res = prefix[K-1]+1;
    for(char j=0; j<26; j++){
      for(int k=j+1; k<26; k++){
        int l=(P[j]-'a')*26+P[k]-'a';
        auto m=former[K-1].find(l);
        if(m != former[K-1].end())
           res += m->second;
      }
    }
    cout << res << endl;
  }


  return 0;
}

Submission Info

Judge Result