Submission #972167

#	Time	Username	Problem	Language	Result	Execution time	Memory
972167		duckindog	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	269 ms	22100 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

const int N = 5'000 + 10,
          base = 19937;
int n, m;

using ull = unsigned long long;
ull pw[N];
struct Hash {
  int n;
  vector<ull> h;

  Hash() {}
  Hash(string s) : n(s.size()), h(s.size() + 1) { 
    pw[0] = 1;
    for (int i = 1; i <= n; ++i) {
      h[i] = h[i - 1] * base + s[i - 1];
      pw[i] = pw[i - 1] * base;
    }
  }
  ull get(int l, int r) { return h[r] - h[l - 1] * pw[r - l + 1]; }
} h[N];

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m;

  for (int i = 1; i <= n; ++i) { 
    string s; cin >> s;
    h[i] = Hash(s);
  }

  while (m--) { 
    string st, ed; cin >> st >> ed;
    
    Hash s(st), e(ed);

    int answer = 0;
    for (int i = 1; i <= n; ++i) { 
      if (h[i].n < s.n || h[i].n < e.n) continue;

      answer += (h[i].get(1, s.n) == s.get(1, s.n) 
                  && h[i].get(h[i].n - e.n + 1, h[i].n) == e.get(1, e.n));
    }
    cout << answer << "\n";
  }

}

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