#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
#define f first
#define s second
#define mp make_pair
#define sz(x) (int)x.size()
#define pb push_back
#define ins insert
const int MOD = 1e9+7;
const int mx = 200005;
int b[2];
int ib[2];
int modpow(int b, ll p){
int val = 1;
for(ll g = b; p > 0; g = (g*g) % MOD){
if(p % 2 == 1){
val = (g*val) % MOD;
}
p/=2;
}
return val;
}
struct HashRange {
int n;
vi csum[2];
vi pows[2];
vi ipows[2];
HashRange(){
}
void init(string S){
n = sz(S);
S = "#"+S;
csum[0] = csum[1] = pows[0] = pows[1] = ipows[0] = ipows[1] = vi(n+1, 0);
pows[0][0] = pows[1][0] = ipows[0][0] = ipows[1][0] = 1;
pows[0][1] = b[0];
pows[1][1] = b[1];
ipows[0][1] = ib[0];
ipows[1][1] = ib[1];
for(int i = 2; i <= n; i++){
for(int j = 0; j < 2; j++){
pows[j][i] = (ll(pows[j][i-1])*b[j]) % MOD;
ipows[j][i] = (ll(ipows[j][i-1])*ib[j]) % MOD;
}
}
for(int i = 1; i <= n; i++){
for(int j = 0; j < 2; j++){
csum[j][i] = (ll(csum[j][i-1]) + ll(pows[j][i])*int(S[i])) % MOD;
}
}
}
ll hash(int l, int r){
r++;
int val0 = ((ll(csum[0][r])-csum[0][l])*ipows[0][l]) % MOD;
int val1 = ((ll(csum[1][r])-csum[1][l])*ipows[1][l]) % MOD;
val0 = (val0+MOD) % MOD;
val1 = (val1+MOD) % MOD;
return ll(val0)*MOD + val1;
}
};
int N, M;
string S[mx];
HashRange Shash[mx];
HashRange Phash[mx];
HashRange Qhash[mx];
string P[mx];
string Q[mx];
pi rang[mx]; // range of P for each query
map<ll, int> m;
unordered_set<ll> us;
vi poses[mx];
bool Sless(int a, int b){
return S[a] < S[b];
if(S[a][0] != S[b][0]){
return S[a][0] < S[b][0];
}
int lo = 1;
int hi = min(sz(S[a]), sz(S[b]));
while(lo < hi){
int mid = (lo+hi)/2+1;
if(Shash[a].hash(0, mid-1) == Shash[b].hash(0, mid-1)){
lo = mid;
}
else hi = mid-1;
}
if(lo == sz(S[a]) && lo == sz(S[b])){
return false;
}
if(lo == sz(S[a])){
return true;
}
if(lo == sz(S[b])){
return false;
}
return S[a][lo] < S[b][lo];
}
bool Pcmpless(int p, int s){ //P[p] <= S[s]
if(P[p][0] != S[s][0]){
return P[p][0] <= S[s][0];
}
int lo = 1;
int hi = min(sz(P[p]), sz(S[s]));
while(lo < hi){
int mid = (lo+hi)/2+1;
if(Phash[p].hash(0, mid-1) == Shash[s].hash(0, mid-1)){
lo = mid;
}
else hi = mid-1;
}
if(lo == sz(P[p]) && lo == sz(S[s])){
return true;
}
if(lo == sz(P[p])){
return true;
}
if(lo == sz(S[s])){
return false;
}
return P[p][lo] <= S[s][lo];
}
bool Pcmpgreat(int p, int s){ //P[p] >= S[s]
if(P[p][0] != S[s][0]){
return P[p][0] >= S[s][0];
}
int lo = 1;
int hi = min(sz(P[p]), sz(S[s]));
while(lo < hi){
int mid = (lo+hi)/2+1;
if(Phash[p].hash(0, mid-1) == Shash[s].hash(0, mid-1)){
lo = mid;
}
else hi = mid-1;
}
if(lo == sz(P[p]) && lo == sz(S[s])){
return true;
}
if(lo == sz(P[p])){
return false;
}
if(lo == sz(S[s])){
return true;
}
return P[p][lo] >= S[s][lo];
}
void ps(int a){
cout << a << "\n";
}
clock_t c;
int cur = 0;
void w(){
cout << "B" << ++cur << " " << double(clock()-c)/CLOCKS_PER_SEC << "\n";
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
c = clock();
//w();
b[0] = rand() % (MOD/5*4) + MOD/10;
b[1] = rand() % (MOD/5*4) + MOD/10;
ib[0] = modpow(b[0], MOD-2);
ib[1] = modpow(b[1], MOD-2);
cin >> N >> M;
for(int i = 1; i <= N; i++){
cin >> S[i];
Shash[i].init(S[i]);
}
//w();
for(int i = 1; i <= M; i++){
cin >> P[i] >> Q[i];
Phash[i].init(P[i]);
Qhash[i].init(Q[i]);
}
//w();
//make a hash struct for pair of ints -- DONE
// HashRange a;
// a.init("ABCABCABC");
// cout << a.hash(0, 2).f << " " << a.hash(0, 2).s << "\n";
// cout << a.hash(1, 3).f << " " << a.hash(1, 3).s << "\n";
// cout << a.hash(3, 5).f << " " << a.hash(3, 5).s << "\n";
//sort all S strings -- DONE
vi Sstrs;
for(int i = 1; i <= N; i++){
Sstrs.pb(i);
}
sort(Sstrs.begin(), Sstrs.end(), [](int a, int b){return Sless(a, b);}); //maybe can't compare equals?
vector<string> Shelp(N+1);
//w();
for(int i = 0; i < N; i++){
Shelp[i+1] = S[Sstrs[i]];
}
for(int i = 1; i <= N; i++){
S[i] = Shelp[i];
Shash[i].init(S[i]);
//cout << S[i] << "\n"; --> should be sorted
}
//w();
//Each P[i] is a range of S, Q[i] --> hash val. Edit rang
for(int i = 1; i <= M; i++){
if(Pcmpless(i, N) == false){
rang[i].f = N+1;
continue;
}
int lo = 1;
int hi = N;
while(lo < hi){
int mid = (lo+hi)/2;
if(Pcmpless(i, mid)){
hi = mid;
}
else lo = mid+1;
}
if(sz(S[lo]) < sz(P[i]) || Shash[lo].hash(0, sz(P[i])-1) != Phash[i].hash(0, sz(P[i])-1)){
rang[i].f = N+1;
continue;
}
rang[i].f = lo;
hi = N;
while(lo < hi){
int mid = (lo+hi)/2+1;
if(sz(S[mid]) < sz(P[i]) || Shash[mid].hash(0, sz(P[i])-1) != Phash[i].hash(0, sz(P[i])-1)){
hi = mid-1;
}
else lo = mid;
}
rang[i].s = lo;
}
//w();
//Go through every suffix, if it's relevant insert index into a vector
for(int i = 1; i <= M; i++){
m[Qhash[i].hash(0, sz(Q[i])-1)];
us.ins(Qhash[i].hash(0, sz(Q[i])-1));
}
//w();
int cnt = 0;
for(auto &u: m){
u.s = ++cnt;
}
for(int i = 1; i <= N; i++){
for(int j = sz(S[i])-1; j >= 0; j--){
if(us.count(Shash[i].hash(j, sz(S[i])-1))){
poses[m[Shash[i].hash(j, sz(S[i])-1)]].pb(i);
}
}
}
//w();
//for every range and Q[i], binary search for # of suffixes that work for each
for(int i = 1; i <= M; i++){
pi r = rang[i];
int vind = m[Qhash[i].hash(0, sz(Q[i])-1)];
int ans = 0;
if(sz(poses[vind]) == 0 || r.s < poses[vind][0] || r.f > poses[vind].back()){
ps(0);
continue;
}
pi works;
int lo = 0;
int hi = sz(poses[vind])-1;
while(lo < hi){
int mid = (lo+hi)/2;
if(r.f <= poses[vind][mid]){
hi = mid;
}
else lo = mid+1;
}
works.f = lo;
lo = 0;
hi = sz(poses[vind])-1;
while(lo < hi){
int mid = (lo+hi)/2+1;
if(poses[vind][mid] <= r.s){
lo = mid;
}
else hi = mid-1;
}
works.s = hi;
if(works.f > works.s){
ps(0);
continue;
}
ans = works.s-works.f+1;
ps(ans);
}
w();
//cout << inittime << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
113144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
345 ms |
237048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
206 ms |
144120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
113144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
