Submission #748215

#	Time	Username	Problem	Language	Result	Execution time	Memory
748215		oscarsierra12	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	600 ms	368156 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std ;

#define ff    first
#define ss    second
#define pb    push_back

typedef long long    ll;
typedef pair<ll,ll>    ii;
typedef long double    lf;

const int N = 5e6;

const static int alpha = 26;
int trie[N][alpha], fail[N], nodes;
int matches[N];
vector <int> end_word[N];
int ans[N];
stack<int> st;

void add(string &s, int i) {
  int cur = 0;
  for(char c : s) {
    int x = c-'A';
    if(!trie[cur][x]) trie[cur][x] = ++nodes;
    cur = trie[cur][x];
  }
  //cnt_word[cur]++;
  end_word[cur].pb(i); // for i > 0
}

void build() {
  queue<int> q; q.push(0);
  while(q.size()) {
    int u = q.front(); q.pop();
    st.push(u);
    for(int i = 0; i < alpha; ++i) {
      int v = trie[u][i];
      if(!v) trie[u][i] = trie[ fail[u] ][i]; // construir automata
      else q.push(v);
      if(!u || !v) continue;
      fail[v] = trie[ fail[u] ][i];
      //fail_out[v] = end_word[ fail[v] ] ? fail[v] : fail_out[ fail[v] ];
      //cnt_word[v] += cnt_word[ fail[v] ]; // obtener informacion del fail_padre
    }
  }
}

void prop() { 
  while (st.size()) { 
     int u = st.top(); st.pop();
     for (auto &e : end_word[u]) ans[e] = matches[u];
     matches[fail[u]]+=matches[u];
  }
}

int main() {

  #ifdef LOCAL
  freopen("input.txt","r",stdin);
//  freopen("output.txt","w",stdout);
  #endif // LOCAL

  ios_base::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  
  int n, m; cin >> n >> m;
  //return 0;
  vector <string> s(n);
  for (auto &e : s) cin >> e;
  
  for (int i = 0; i < m; ++i) { 
     string prf, suf;
     cin >> prf >> suf;
     suf.pb('Z');
     suf = suf + prf;
     add(suf, i);
  }
  build();
  for (int i = 0; i < n; ++i) { 
     s[i] = s[i] + "Z" + s[i];
     int node = 0;
     for (auto &e : s[i]) 
        node = trie[node][e - 'A'], matches[node]++;
  }
  prop();
  
  for (int i = 0; i < m; ++i) cout << ans[i] << '\n';
  
  return 0;
}

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