fork download

copy

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
struct suffix_array {
 
    string s;
    int n;
    vector<int> c, p;
    suffix_array(string s){
        s += '$';
        this->s = s;
        this->n = s.length();
        int n = s.length();
        vector<int> c(n, 0), p(n, 0), cnt(max(n, 256), 0);
        for(char x : s) cnt[x]++;
        for(int i = 1; i < 256; i++) cnt[i] += cnt[i-1];
        for(int i = 0; i < n; i++) p[--cnt[s[i]]] = i;
        c[p[0]] = 0;
        for(int i = 1; i < n; i++) c[p[i]] = (s[p[i]] != s[p[i-1]]) ? c[p[i-1]] + 1 : c[p[i-1]];
        for(int i = 2; i <= 2*n; i <<= 1){
            vector<pair<int, int>> v;
            vector<int> pn = p, cn = c;
            for(int j = 0; j < n; j++){
                v.push_back({j, (j + i/2)%n});
            }
            for(int &j : cnt) j = 0;
            for(int j = 0; j < n; j++) cnt[c[v[j].second]]++;
            for(int j = 1; j < n; j++) cnt[j] += cnt[j-1];
            for(int j = 0; j < n; j++) pn[--cnt[c[v[j].second]]] = j;
            for(int &j : cnt) j = 0;
            for(int j = 0; j < n; j++) cnt[c[pn[j]]]++;
            for(int j = 1; j < n; j++) cnt[j] += cnt[j-1];
            for(int j = 0; j < n; j++) p[--cnt[c[pn[n-1-j]]]] = pn[n-1-j];
            cn[p[0]] = 0;
            int classes = 1;
            for (int j = 1; j < n; j++) {
                pair<int, int> cur = {c[p[j]], c[(p[j] + i/2) % n]};
                pair<int, int> prev = {c[p[j-1]], c[(p[j-1] + i/2 + n) % n]};
                if (cur != prev) ++classes;
                cn[p[j]] = classes - 1;
            }
            c.swap(cn);
        }
        // c.pop_back();
        // for(int &x : c) x--;
        // p.erase(p.begin());
        this->p = p;
        this->c = c;
    }
 
    void prt(){
        for(int x : p) cout << x << " ";
        cout << endl;
    }
 
    int first_occ(string x){
        int l = 0, r = n-1, ans = -1;
        while(l <= r){
            int mid = (l + r)/2;
            string sub = s.substr(p[mid], min(s.length() - p[mid], x.length()));
            if(sub >= x){
                if(sub == x) ans = mid;
                r = mid-1;
            } else {
                l = mid+1;
            }
        }
        return ans;
    }
 
    bool exist(string x){
        int l = 0, r = n-1, ans = -1;
        while(l <= r){
            int mid = (l + r)/2;
            string sub1 = s.substr(p[mid], s.length() - p[mid]);
            string sub = sub1.substr(0, min(sub1.length(), x.length()));
            if(sub >= x){
                if(sub == x) ans = mid;
                r = mid-1;
            } else {
                l = mid+1;
            }
        }
        return (ans != -1);
    }
 
};
 
char buf[300010];
 
string read(){
    scanf("%s", buf);
    return buf;
}
 
int main(){
 
    string s = read();
    suffix_array suf(s);
 
    int q;
    scanf("%d", &q);
    while(q--){
        string x = read();
        puts(suf.exist(x) ? "Yes" : "No");
    }
 
 
}
 

Main.java:1: error: illegal character: '#'
#include <bits/stdc++.h>
^
Main.java:1: error: class, interface, or enum expected
#include <bits/stdc++.h>
         ^
Main.java:4: error: class, interface, or enum expected
using ll = long long;
^
Main.java:6: error: class, interface, or enum expected
struct suffix_array {
^
Main.java:9: error: class, interface, or enum expected
    int n;
    ^
Main.java:10: error: class, interface, or enum expected
    vector<int> c, p;
    ^
Main.java:11: error: class, interface, or enum expected
    suffix_array(string s){
    ^
Main.java:13: error: class, interface, or enum expected
        this->s = s;
        ^
Main.java:14: error: class, interface, or enum expected
        this->n = s.length();
        ^
Main.java:15: error: class, interface, or enum expected
        int n = s.length();
        ^
Main.java:16: error: class, interface, or enum expected
        vector<int> c(n, 0), p(n, 0), cnt(max(n, 256), 0);
        ^
Main.java:17: error: class, interface, or enum expected
        for(char x : s) cnt[x]++;
        ^
Main.java:18: error: class, interface, or enum expected
        for(int i = 1; i < 256; i++) cnt[i] += cnt[i-1];
        ^
Main.java:18: error: class, interface, or enum expected
        for(int i = 1; i < 256; i++) cnt[i] += cnt[i-1];
                       ^
Main.java:18: error: class, interface, or enum expected
        for(int i = 1; i < 256; i++) cnt[i] += cnt[i-1];
                                ^
Main.java:19: error: class, interface, or enum expected
        for(int i = 0; i < n; i++) p[--cnt[s[i]]] = i;
        ^
Main.java:19: error: class, interface, or enum expected
        for(int i = 0; i < n; i++) p[--cnt[s[i]]] = i;
                       ^
Main.java:19: error: class, interface, or enum expected
        for(int i = 0; i < n; i++) p[--cnt[s[i]]] = i;
                              ^
Main.java:20: error: class, interface, or enum expected
        c[p[0]] = 0;
        ^
Main.java:21: error: class, interface, or enum expected
        for(int i = 1; i < n; i++) c[p[i]] = (s[p[i]] != s[p[i-1]]) ? c[p[i-1]] + 1 : c[p[i-1]];
        ^
Main.java:21: error: class, interface, or enum expected
        for(int i = 1; i < n; i++) c[p[i]] = (s[p[i]] != s[p[i-1]]) ? c[p[i-1]] + 1 : c[p[i-1]];
                       ^
Main.java:21: error: class, interface, or enum expected
        for(int i = 1; i < n; i++) c[p[i]] = (s[p[i]] != s[p[i-1]]) ? c[p[i-1]] + 1 : c[p[i-1]];
                              ^
Main.java:22: error: class, interface, or enum expected
        for(int i = 2; i <= 2*n; i <<= 1){
        ^
Main.java:22: error: class, interface, or enum expected
        for(int i = 2; i <= 2*n; i <<= 1){
                       ^
Main.java:22: error: class, interface, or enum expected
        for(int i = 2; i <= 2*n; i <<= 1){
                                 ^
Main.java:24: error: class, interface, or enum expected
            vector<int> pn = p, cn = c;
            ^
Main.java:25: error: class, interface, or enum expected
            for(int j = 0; j < n; j++){
            ^
Main.java:25: error: class, interface, or enum expected
            for(int j = 0; j < n; j++){
                           ^
Main.java:25: error: class, interface, or enum expected
            for(int j = 0; j < n; j++){
                                  ^
Main.java:27: error: class, interface, or enum expected
            }
            ^
Main.java:29: error: class, interface, or enum expected
            for(int j = 0; j < n; j++) cnt[c[v[j].second]]++;
            ^
Main.java:29: error: class, interface, or enum expected
            for(int j = 0; j < n; j++) cnt[c[v[j].second]]++;
                           ^
Main.java:29: error: class, interface, or enum expected
            for(int j = 0; j < n; j++) cnt[c[v[j].second]]++;
                                  ^
Main.java:30: error: class, interface, or enum expected
            for(int j = 1; j < n; j++) cnt[j] += cnt[j-1];
            ^
Main.java:30: error: class, interface, or enum expected
            for(int j = 1; j < n; j++) cnt[j] += cnt[j-1];
                           ^
Main.java:30: error: class, interface, or enum expected
            for(int j = 1; j < n; j++) cnt[j] += cnt[j-1];
                                  ^
Main.java:31: error: class, interface, or enum expected
            for(int j = 0; j < n; j++) pn[--cnt[c[v[j].second]]] = j;
            ^
Main.java:31: error: class, interface, or enum expected
            for(int j = 0; j < n; j++) pn[--cnt[c[v[j].second]]] = j;
                           ^
Main.java:31: error: class, interface, or enum expected
            for(int j = 0; j < n; j++) pn[--cnt[c[v[j].second]]] = j;
                                  ^
Main.java:32: error: class, interface, or enum expected
            for(int &j : cnt) j = 0;
            ^
Main.java:33: error: class, interface, or enum expected
            for(int j = 0; j < n; j++) cnt[c[pn[j]]]++;
            ^
Main.java:33: error: class, interface, or enum expected
            for(int j = 0; j < n; j++) cnt[c[pn[j]]]++;
                           ^
Main.java:33: error: class, interface, or enum expected
            for(int j = 0; j < n; j++) cnt[c[pn[j]]]++;
                                  ^
Main.java:34: error: class, interface, or enum expected
            for(int j = 1; j < n; j++) cnt[j] += cnt[j-1];
            ^
Main.java:34: error: class, interface, or enum expected
            for(int j = 1; j < n; j++) cnt[j] += cnt[j-1];
                           ^
Main.java:34: error: class, interface, or enum expected
            for(int j = 1; j < n; j++) cnt[j] += cnt[j-1];
                                  ^
Main.java:35: error: class, interface, or enum expected
            for(int j = 0; j < n; j++) p[--cnt[c[pn[n-1-j]]]] = pn[n-1-j];
            ^
Main.java:35: error: class, interface, or enum expected
            for(int j = 0; j < n; j++) p[--cnt[c[pn[n-1-j]]]] = pn[n-1-j];
                           ^
Main.java:35: error: class, interface, or enum expected
            for(int j = 0; j < n; j++) p[--cnt[c[pn[n-1-j]]]] = pn[n-1-j];
                                  ^
Main.java:36: error: class, interface, or enum expected
            cn[p[0]] = 0;
            ^
Main.java:37: error: class, interface, or enum expected
            int classes = 1;
            ^
Main.java:38: error: class, interface, or enum expected
            for (int j = 1; j < n; j++) {
            ^
Main.java:38: error: class, interface, or enum expected
            for (int j = 1; j < n; j++) {
                            ^
Main.java:38: error: class, interface, or enum expected
            for (int j = 1; j < n; j++) {
                                   ^
Main.java:40: error: class, interface, or enum expected
                pair<int, int> prev = {c[p[j-1]], c[(p[j-1] + i/2 + n) % n]};
                ^
Main.java:41: error: class, interface, or enum expected
                if (cur != prev) ++classes;
                ^
Main.java:42: error: class, interface, or enum expected
                cn[p[j]] = classes - 1;
                ^
Main.java:43: error: class, interface, or enum expected
            }
            ^
Main.java:45: error: class, interface, or enum expected
        }
        ^
Main.java:50: error: class, interface, or enum expected
        this->c = c;
        ^
Main.java:51: error: class, interface, or enum expected
    }
    ^
Main.java:55: error: class, interface, or enum expected
        cout << endl;
        ^
Main.java:56: error: class, interface, or enum expected
    }
    ^
Main.java:60: error: class, interface, or enum expected
        while(l <= r){
        ^
Main.java:62: error: class, interface, or enum expected
            string sub = s.substr(p[mid], min(s.length() - p[mid], x.length()));
            ^
Main.java:63: error: class, interface, or enum expected
            if(sub >= x){
            ^
Main.java:65: error: class, interface, or enum expected
                r = mid-1;
                ^
Main.java:66: error: class, interface, or enum expected
            } else {
            ^
Main.java:68: error: class, interface, or enum expected
            }
            ^
Main.java:71: error: class, interface, or enum expected
    }
    ^
Main.java:75: error: class, interface, or enum expected
        while(l <= r){
        ^
Main.java:77: error: class, interface, or enum expected
            string sub1 = s.substr(p[mid], s.length() - p[mid]);
            ^
Main.java:78: error: class, interface, or enum expected
            string sub = sub1.substr(0, min(sub1.length(), x.length()));
            ^
Main.java:79: error: class, interface, or enum expected
            if(sub >= x){
            ^
Main.java:81: error: class, interface, or enum expected
                r = mid-1;
                ^
Main.java:82: error: class, interface, or enum expected
            } else {
            ^
Main.java:84: error: class, interface, or enum expected
            }
            ^
Main.java:87: error: class, interface, or enum expected
    }
    ^
Main.java:91: error: class, interface, or enum expected
char buf[300010];
^
Main.java:93: error: class, interface, or enum expected
string read(){
^
Main.java:95: error: class, interface, or enum expected
    return buf;
    ^
Main.java:96: error: class, interface, or enum expected
}
^
Main.java:101: error: class, interface, or enum expected
    suffix_array suf(s);
    ^
Main.java:103: error: class, interface, or enum expected
    int q;
    ^
Main.java:104: error: class, interface, or enum expected
    scanf("%d", &q);
    ^
Main.java:105: error: class, interface, or enum expected
    while(q--){
    ^
Main.java:107: error: class, interface, or enum expected
        puts(suf.exist(x) ? "Yes" : "No");
        ^
Main.java:108: error: class, interface, or enum expected
    }
    ^
88 errors

Standard output is empty