Hi. Any ideas what they put inside the test file to #3?

If you have WA 13, try this test:
1
a
1
b....ba , where b repeated ~130000 times

If you've got rte 27: m can be more than 10000

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;
}

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;
}

create suffix links...

Some testcases contain empty strings, which is very nasty, and they should be read in combination with scanf and gets. I had scanf("%d\n", &N) initially, which skipped the empty lines afterwards, so my gets() calls where kind of useless.

Secondly, here are some testcases:

2
bc
abcd
1
abcx

Should return 1 2

2
bc
abcd
1
abcd

Should return 1 1

Check my submissions and learn how evil the problem is!

I had a MLE 7 test - I split the tree into 3 parts
And choose the best 3 answers
Accepted 0.593 !!!!

-------------------------
Enough for the division into 2 parts

Edited by author 30.07.2011 10:18

The new time limit is 1.0 seconds (old - 0.5s). All submissions have been rejudged. The number of authors who has AC remain almost the same.

What is real TL?
In statements it is 0.5s, but in solutions rating there are solutions which passed with time bigger than 0.5s.

can somebody explain how the example shown has answer as
6 33
and not
6 44?
are we not supposed to give the word position?

why authors didn't rejudge???
some authors got accepted more than 0.5 sec....
i don't understand why?

Edited by author 04.06.2014 19:39

WA 30. Can anyone help me? Or just give AC code? I have spent to much time on this problem.
email: LegionN7@i.ua

Update:
Accepted.

Edited by author 05.03.2014 18:52

TL for this problem is 0.5s but list of successful submissions contains times up to 2s.

Initially, in one trie node i stored:

Node child, sibling, sufLink;
byte parSymb; short lEnd;

This is 4 * 3 + 1 + 2 = 15 bytes per node, ML 28.

Then I used static array of nodes(maximum number of nodes is 99991), memory consumption per node is the same(instead of Node reference we store int), ML 28.

At the end, I stored child, sibling, sufLink and parSymb(we need 17 bits for each memory pointer and 8 bits for parent symbol, 17 * 3 + 8 = 59 bits in total) in one long, and lEnd in short, only 10 bytes per node, and got AC!

I use Aho Corasick algorithm but get "Wrong answer 3". Why? Please give me test 3.

Edited by author 23.11.2012 13:28

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException  {
        Scanner sc = new Scanner(System.in);
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = sc.nextInt();
        String S[] = new String[n];
        for (int i = 0; i < n; i++) {
            S[i] = sc.next();
        }
        int m = sc.nextInt();
        String[] S2 = new String[m];
        for (int i = 0; i < m; i++) {
            S2[i] = bf.readLine();
        }


        int count = 0, tempcont = 0;
        boolean isFineded = false;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {

                StringTokenizer st = new StringTokenizer(S2[i]);
                count -= tempcont;
                tempcont = 0;
                while (st.hasMoreTokens()) {
                    tempcont++;
                    String temp = st.nextToken();
                    if (isExits(temp, S[j])) {
                        count++;
                        isFineded = true;
                        System.out.println(i + 1 + " " + count);
                    } else {
                        count++;
                    }
                }
            }
            tempcont = 0;
        }

        if (isFineded == false) {
            System.out.println("Passed");
        }

    }
    static boolean isExits(String src, String str) {
        boolean bol=false;
        if (str.length() > src.length()) {
            return false;
        } else if (str.equals(src)) {
            return true;
        } else {
            for (int i = 0; i <= src.length() - str.length(); i++) {
                if (str.equals(src.substring(i, i + str.length()))) {
                    bol=true;
                }
                }
            return bol;
        }

    }
}

2
sweet
dream
3
swee
t drea
m

Correct answer is Passed