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

create suffix links...

Check my submissions and learn how evil the problem is!

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.

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

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

What's wrong with test 3? My programm passes everything, that has ever been suggested on this forum. Could you give another test for me? Can WA mean that text is bigger than 10000 symbols, as I declare(because I have Compillation error in case of t[100000] for some reason)? Sorry for my bad english.

const
        maxn=100000;
var
        st,en,n,i,j,k,now,tot,m,tmp,o,ans:longint;
        s:ansistring;
        r,d,failed,fa,h:array[0..maxn]of longint;
        w:array[1..maxn,1..2]of longint;
        target:array[0..maxn]of boolean;
function min(x,y:longint):longint;
begin
        if x<y then exit(x) else exit(y);
end;
begin
        readln(n);
        for n:=1 to n do begin
                readln(s);
                now:=0;
                for j:=1 to length(s) do begin
                        i:=r[now];
                        while i<>0 do begin
                                if w[i,1]=ord(s[j]) then begin
                                        now:=i;
                                        break;
                                end;
                                i:=w[i,2];
                        end;
                        if i=0 then begin
                                inc(tot);
                                fa[tot]:=now;
                                w[tot,1]:=ord(s[j]);
                                w[tot,2]:=r[now];
                                r[now]:=tot;
                                h[tot]:=h[now]+1;
                                now:=tot;
                        end;
                end;
                target[now]:=true;
        end;
        st:=0;
        d[1]:=0;
        en:=1;
        repeat
                inc(st);
                i:=r[d[st]];
                while i<>0 do begin
                        inc(en);
                        d[en]:=i;
                        i:=w[i,2];
                end;
        until st=en;
        for j:=2 to en do begin
                k:=fa[d[j]];
                i:=0;
                while (i=0)and(k<>0) do begin
                        k:=failed[k];
                        i:=r[k];
                        while i<>0 do begin
                                if w[i,1]=w[d[j],1] then break;
                                i:=w[i,2];
                        end;
                end;
                failed[d[j]]:=i;
                if target[i] then begin
                        if not target[d[j]] then h[d[j]]:=min(h[d[j]],h[i]);
                        target[d[j]]:=target[d[j]] or target[i];
                end;
        end;
        failed[0]:=-1;
        readln(m);
        for m:=1 to m do begin
                readln(s);
                ans:=length(s)+1;
                now:=0;
                for j:=1 to length(s) do begin
                        k:=now;
                        i:=0;
                        while (i=0)and(k<>-1) do begin
                                i:=r[k];
                                while i<>0 do begin
                                        if w[i,1]=ord(s[j]) then break;
                                        i:=w[i,2];
                                end;
                                if i=0 then k:=failed[k];
                        end;
                        now:=i;
                        if target[now] then ans:=min(ans,j-h[now]+1);
                end;
                if ans<length(s) then break;
        end;
        if ans<=length(s) then begin
                writeln(m,' ',ans);
        end else writeln('Passed');
end.

I tested my solution on some more hard tests, and it's working on it. But i have WA2. What's the problem with it?