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 have used getchar(),but still WA 5#,why??

Or give me the test data...

Edited by author 30.01.2011 19:21

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?

DO NOT output just after you've find a match.
some short string may be matched before long string,as this:

2
qwertyuiopxyz
uiop
1
qwertyuiopxyzzzz

output 1 1,not 1 7.
luckly,some good AC subroutine can avoid this...

Anybody have got this resul, too? Could you tell why have I WA 15?

Try using aho-corasic with a treap (as a goto map).

Crash (access violation) №2

Could it be because of reading ???
I use Aho-Corasick

I'm reading :

while((ch=getchar())!='\n')
{
   //
   //
}

Edited by author 04.05.2011 20:25

How to read data in Dev c++? I used so many methods: getchar (), gets (), getline (cin, ), scanf (), cin >>.... Now I'm using fgets (str, maxlen, stdin).
These strings from my cod:
fscanf (stdin, "%d\n", &n);
for (0...n - 1)
{
      fgets (s, 10000, stdin);
      ...................
..................
.....................
}
scanf ("%d", &m);
for (0...m - 1)
{
                  fgets (t, 1000000, stdin);
.........
..........
............
}

I have a WA on a test '5'. If you have some tests, please wright.
Thanks for attention! =)

I can't find mistakes. Please help!
var
m:array[1..10000]of string;
m1:string;
a,b,c,d,i,j,k:integer;
begin
readln(a);
for i:=1 to a do
readln(m[i]);
readln(b);
for i:=1 to b do
begin
c:=0;
d:=100000000;
readln(m1);
for j:=1 to a do
if((pos(m[j],m1)>0)) then
begin
c:=pos(m[j],m1);
if(c<d)then d:=c;
end;
if(d<>100000000)then begin
writeln(i,' ',d);
exit;
end;
end;
writeln('Passed');
end.

#include <iostream>
#include <queue>
#include <map>
using namespace std;
#define MAX 2000000
#define K 128

    map<int,int> Next;

    short link[MAX];
    bool leaf[MAX];
    short p[MAX];
    char I[MAX];

int sz,n,m,vv=0;
unsigned char ch;
char chh;
queue<short> q;

int main(){
    p[0] = 0;
    sz = 1;
    scanf("%d",&n);getchar();
    while(n--){
        int v=0;
        while((ch=getchar())!='\n')    {
            if (Next[v*1000+ch] == 0){
                p[sz] = v;
                I[sz] = ch;
                Next[v*1000+ch] = sz++;
            }
            v = Next[v*1000+ch];
        }
        leaf[v] = true;
    }

~8400Kb

Wrong bor ??

7
cccffabab
ccffabab
cffabab
ffabab
abab
bab
fab
1
cccffabaj

answer 1 5

for this test:

2
bc
abcd
1
abcd

?

Upd: turned up to be 1 1

Also, if you have WA 6, check this test:

1

1


//there is 1 space in second line and 2 spaces in fourth line

Edited by author 17.04.2011 12:52

Of cource this problem can be solved using Aho Corasick algorithm. But there is another much more simple, but not determenistic solution. A hash function can be used to compare substrings of the text and the words. First we should find the hash function for all the words. Then we should evaluate the hash function for each substring of the text that has the same length as some word. And finaly comparing this this values of hash functions gives us the answer.

There exists some symbol whose ascll is negative!!!!

topic

Can anyone give me an advice, how to build aho-corasick algorithm, that's using a compressed suffix tree. I wrote one, but it uses uncompressed tree, which results in MLE on test 7. I understood, how to build the compressed tree, but have no idea, how to cooperate it with aho-corasick.

P.S. I bind my compressed suffix tree realisation, if someone will be interesed.


#include <cstdio>

using namespace std;

typedef unsigned short id;
typedef unsigned char uc;
typedef unsigned int ui;

const id DICT_SIZE = 10005, NONE = DICT_SIZE + 1;

ui N, M;

uc wbuf[100001];
ui wbs;
uc buf [900001];
ui bfs;

void get_line() {
    bfs = 0;
    uc ch = getchar();
    while (ch != '\n') {
        buf[bfs] = ch;
        ch = getchar();
        bfs++;
    }
}

void get_word() {
    uc ch = getchar();
    while (ch != '\n') {
        if (ch != 0 && ch != '\r') {
            wbuf[wbs] = ch;
            wbs++;
        }
        ch = getchar();
    }
}

struct pstr {
    id start, end;

    pstr() {
        start = end = 0;
    }

    pstr(ui s, ui e) {
        start = s;
        end = e;
    }

    int len() {
        return end - start;
    }

    void cut_begin(ui s) {
        start = start + s;
    }

    void cut_end(ui e) {
        end = start + e;
    }

    void print() {
        for (int i = 0; i < len(); i++)putchar((*this)[i]);
        putchar('\n');
    }
    uc & operator[](ui);
    pstr & operator=(const pstr);
};

uc & pstr::operator[](ui i) {
    return wbuf[start + i];
}

pstr& pstr::operator =(const pstr p) {
    this->end = p.end;
    this->start = p.start;
    return *this;
}

struct vert {
    pstr p;
    id length, parent, index, g [256];
    uc ac;
    bool leaf;
    id & operator[](uc);
    void addstr(pstr & b, id & wlen);
    vert & c(uc);

    void init(id ind) {
        for (id i = 0; i < 256; i++)
            g[i] = NONE;
        index = ind;
    }

    void print() {
        printf("index=%d ac='%c' parent=%d leaf=%d p: ", index, ac, parent, leaf);
        p.print();
    }
    bool search(uc * str, ui &st, ui & size);
};
vert dict [DICT_SIZE + 2]; //0 - root
id dinc = 1;

id & vert::operator[](uc ch) {
    return g[ch];
}

id create_vect() {
    dict[dinc].init(dinc);
    dinc++;
    return dinc - 1;
}

vert & vert::c(uc ch) {
    return dict[g[ch]];
}

void vert::addstr(pstr & b, id & wlen) {
    ui i;
    for (i = 0; b[i] == p[i] && i < p.len() && i < b.len(); i++);
    if (i == p.len()) {//p - полностью подстрока b
        if (g[b[i]] != NONE) {
            if (b.len() == i) {
                leaf = true;
                length = wlen;
            } else {
                id ind = g[b[i]];
                b.cut_begin(i + 1);
                dict[ind].addstr(b, wlen);
            }
        } else {
            if (b.len() == i) {
                leaf = true;
                length = wlen;
            } else {
                id n = create_vect();
                g[b[i]] = n;
                vert & v = dict[n];
                v.ac = b[i];
                v.p = b;
                v.p.cut_begin(i + 1);
                v.parent = index;
                v.leaf = true;
                v.length = wlen;
            }
        }
    } else {
        id n = create_vect();
        dict[parent][ac] = n;
        vert & nv = dict[n];
        nv.p = p;
        nv.p.cut_end(i);
        nv.parent = parent;
        nv.ac = ac;
        nv.g[p[i]] = index;
        ac = p[i];
        parent = n;
        p.cut_begin(i + 1);
        if (i == b.len()) {
            nv.leaf = true;
            nv.length = wlen;
        } else {
            id w = create_vect();
            vert & wv = dict[w];
            wv.p = b;
            wv.p.cut_begin(i + 1);
            wv.parent = n;
            wv.ac = b[i];
            wv.leaf = true;
            wv.length = wlen;
            nv.g[b[i]] = w;
        }
    }
}

int main(int argc, char** argv) {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    scanf("%u", &N);
    getchar();
    wbs = 0;
    dict[0].init(0);
    dict[NONE].init(NONE);
    for (ui i = 0; i < N; i++) {
        ui _wbs = wbs;
        get_word();
        pstr ps(_wbs, wbs);
        if (ps.len() == 0)continue;
        id wlen = ps.len();
        dict[0].addstr(ps, wlen);
    }
    for (ui i = 0; i < dinc; i++)dict[i].print();
    //previous line prints the result of suffix tree building
    scanf("%u", &M);
    getchar();
    for (ui k = 0; k < M; k++) {
        get_line();
        if (bfs == 0)continue;
        for (ui i = 0; i < bfs; i++) {

        }
    }
    printf("Passed");
    return 0;
}

Better way to view: http://pastebin.com/M6TUztjc

Edited by author 03.11.2010 23:30

Can anybody give me some good test?
I can't find any bug

Admins,i think i need you help

Any ideas?