Discussion @ 1269. Obscene Words Filter @ Timus Online Judge

AGorohov WTF?! Memory limit exceeded && Time limit // Problem 1269. Obscene Words Filter 14 Feb 2025 01:13

sailingoat Aho Carasick // Problem 1269. Obscene Words Filter 29 Jan 2025 22:36

Denis Koshman If you have WA12 [1] // Problem 1269. Obscene Words Filter 25 Aug 2008 19:08

foxlup Passed or [1] // Problem 1269. Obscene Words Filter 11 Jan 2025 04:49

Yury_Semenov RE2 in Rust // Problem 1269. Obscene Words Filter 16 Oct 2024 20:41

Rafal WA #3 :( [7] // Problem 1269. Obscene Words Filter 8 Feb 2007 15:29

Aleksey[TheCrawfish]Bykov'` If you had trouble with 13/27 tests // Problem 1269. Obscene Words Filter 18 Sep 2022 21:42

Dan WA2 suffix array // Problem 1269. Obscene Words Filter 28 Jun 2019 02:09

Why wa2?
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define vc vector

using namespace std;

vc<int> p;
string s;
int n;
void calcSuffixArray() {
    p.resize(n);
    vc<int> c(n), pn(n), cn(n), k(max(256, n));
    for (char ch : s) {
        k[ch]++;
    }
    partial_sum(k.begin(), k.begin() + 256, k.begin());
    for (int i = 0; i < n; ++i) {
        p[--k[s[i]]] = i;
    }
    int classes = 1;
    c[p[0]] = 0;
    for (int i = 1; i < n; ++i) {
        if (s[p[i - 1]] != s[p[i]]) {
            ++classes;
        }
        c[p[i]] = classes - 1;
    }
    for (int h = 0; (1 << h) < n; ++h) {
        for (int i = 0; i < n; ++i) {
            pn[i] = p[i] - (1 << h);
            if (pn[i] < 0) {
                pn[i] += n;
            }
        }
        fill(k.begin(), k.begin() + classes, 0);
        for (int i = 0; i < n; ++i) {
            k[c[pn[i]]]++;
        }
        partial_sum(k.begin(), k.begin() + classes, k.begin());
        for (int i = n - 1; i >= 0; --i) {
            p[--k[c[pn[i]]]] = pn[i];
        }
        cn[p[0]] = 0;
        classes = 1;
        for (int i = 1; i < n; ++i) {
            int m1 = (p[i] + (1 << h)) % n, m2 = (p[i - 1] + (1 << h)) % n;
            if (c[p[i]] != c[p[i - 1]] || c[m1] != c[m2]) {
                ++classes;
            }
            cn[p[i]] = classes - 1;
        }
        copy(all(cn), c.begin());
    }
}

const int INF = int(2e9);

struct SegTree {
    vc<int> t;

    void build(int v, int l, int r) {
        if (l + 1 == r) {
            t[v] = p[l];
            return;
        }
        int m = (l + r) >> 1;
        int nxt = v + ((m - l) << 1);
        build(v + 1, l, m);
        build(nxt, m, r);
        t[v] = min(t[v + 1], t[nxt]);
    }

    SegTree() {
        t.resize(2 * n);
        build(0, 0, n);
    }

    int getMin(int v, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) {
            return t[v];
        }
        int m = (l + r) >> 1;
        int nxt = v + ((m - l) << 1);
        int ans = INF;
        if (ql < m) {
            ans = min(ans, getMin(v + 1, l, m, ql, qr));
        }
        if (m < qr) {
            ans = min(ans, getMin(nxt, m, r, ql, qr));
        }
        return ans;
    }

};

struct comp {
    string t;
    int pos;
    comp(string t) : t(move(t)), pos(0) {}
    bool operator ()(const int& a, const int& b) {
        if (b == -1) {
            return (pos + a < s.size() ? s[a + pos] < t[pos] : true);
        }
        else {
            return (pos + b < s.size() ? t[pos] < s[b + pos] : false);
        }
    }
};

pair<int, int> equalRange(const string& t) {
    int l = 0, r = n;
    comp c(t);
    for (int i = 0; i < t.size() && l < r; ++i) {
        l = lower_bound(p.begin() + l, p.begin() + r, -1, c) - p.begin();
        r = upper_bound(p.begin() + l, p.begin() + r, -1, c) - p.begin();
        c.pos++;
    }
    return make_pair(l, r);
}

void solve() {
    int w;
    cin >> w;
    vc<string> words(w);
    cin.get();
    for (string& i : words) {
        getline(cin, i);
    }
    int rows;
    cin >> rows;
    cin.get();
    vc<int> sz(rows);
    for (int i = 0; i < rows; ++i) {
        string add;
        getline(cin, add);
        add.push_back((i == rows - 1 ? '\0' : '\n'));
        sz[i] = add.size();
        s += add;
    }
    n = s.size();
    calcSuffixArray();

    SegTree tree;
    int ans = INF;
    for (const string& t : words) {
        auto [l, r] = equalRange(t);
        if (l < r) {
            ans = min(ans, tree.getMin(0, 0, n, l, r));
        }
    }

    if (ans == INF) {
        cout << "Passed";
        return;
    }

    for (int i = 0; i < rows; ++i) {
        if (sz[i] <= ans) {
            ans -= sz[i];
        }
        else {
            cout << i + 1 << ' ' << ans + 1 << endl;
            return;
        }
    }
    cout << "WTF";
}

int main() {
    solve();
    return 0;
}

muhammad help with aho corasick MLE 7! [1] // Problem 1269. Obscene Words Filter 18 Sep 2010 22:49

I can't think of a way to store goto and fail transitions of so many vertices and avoid MLE. please help.

here's code:

#include <stdio.h>
#include <queue>
using namespace std;
short g[110000][256];
short f[110000];
short o[110000];
short n,m,newstate=0;
queue<short>Q;
int main(void){
    short i,pos=0,q,r,u,v,ch,state;
    scanf("%hd",&n);getchar();
    for(i=1;i<=n;++i){
        r=0;
        ch=getchar();
        state=0;
        ++r;
        ch+=128;
        while(g[state][ch]){
            state=g[state][ch];
            ch=getchar();
            ++r;
            ch+=128;
        }
        while(ch!='\n'+128){
            newstate=newstate+1;
            g[state][ch]=newstate;
            state=newstate;
            ch=getchar();
            ++r;
            ch+=128;
        }
        o[state]=r-1;
    }
    for(i=0;i<256;++i){
        if(q=g[0][i]){
            f[q]=0;
            Q.push(q);
        }
    }
    while(!Q.empty()){
        r=Q.front();
        Q.pop();
        for(i=0;i<256;++i){
            u=g[r][i];
            if(!(u==0&&r>0)){
                Q.push(u);
                v=f[r];
                while(g[v][i]==0&&v>0) v=f[v];
                f[u]=g[v][i];
                if(o[u]==0) o[u]=o[f[u]];
            }
        }
    }
    scanf("%hd",&m);getchar();
    for(i=1;i<=m;++i){
        q=0;r=0;
        while((ch=getchar())!='\n'){
            ch+=128;
            ++r;
            while(g[q][ch]==0&&q>0) q=f[q];
            q=g[q][ch];
            if(o[q]){
                printf("%hd %hd",i,r-o[q]+1);
                return 0;
            }
        }
    }
    printf("Passed\n");
    return 0;
}

Irakli Khomeriki Re: help with aho corasick MLE 7! // Problem 1269. Obscene Words Filter 21 Sep 2018 23:02

you got pretty close, modified your solution to get AC. let me know if you need hints :) ikhomeriki@gmail.com

Edited by author 21.09.2018 23:04

Artem 8 test // Problem 1269. Obscene Words Filter 11 Aug 2018 00:25

Gary Ye Pitfalls [1] // Problem 1269. Obscene Words Filter 9 Jul 2015 19:59

Mahilewets The problem is really evil. [1] // Problem 1269. Obscene Words Filter 9 Jul 2017 14:29

uu_Innk I had a MLE 7 test - I split the tree into 3 parts - Accepted 0.593 [2] // Problem 1269. Obscene Words Filter 30 Jul 2011 00:43

Vladimir Yakovlev (USU) Time limit update in problem 1269 Obscene Words Filter // Problem 1269. Obscene Words Filter 26 Jun 2016 22:33

Vladimir Leskov`` to admins [1] // Problem 1269. Obscene Words Filter 21 May 2016 20:10

rakeshvarna test case answer [1] // Problem 1269. Obscene Words Filter 4 Feb 2008 23:47

Adhambek To admins // Problem 1269. Obscene Words Filter 26 Jun 2015 19:00

Yerlan Do NOT forget to output the "Passed" - word in the end, for WA#5!!!! // Problem 1269. Obscene Words Filter 29 Dec 2014 17:14

Kirill Luchikhin WA1 // Problem 1269. Obscene Words Filter 4 Jun 2014 19:30

Disintegrator WA 30 // Problem 1269. Obscene Words Filter 3 Mar 2014 21:03

Discussion of Problem 1269. Obscene Words Filter