Can somebody tell me how they passed test nr. 2 (or give me some good test cases)?

I have a solution in O(N*M*log(N*M)) using suffix array and I can't find the bug.

Thanks

Edited by author 16.09.2010 22:39

My solution is based on string hashing. Let's say that the strings from the input are s[1], s[2], ... , s[n]. First, let's iterate over all possible lengths from 1 to 100 (since the maximal length of a string is 100). Let's fix some length "len" and create a vector "all" which will contain all possible hashes of substrings of length "len" of all the strings s[i]. Additionally, for each i from 1 to n create a vector a[i] which will contain the hashes of substrings of length "len" of only the string s[i]. Now, sort all the vectors we've created so that we could binary search on them. Finally, go through each i from 1 to n and then for each of the substrings of s[i], using binary search count the number of occurrences of its hash in the vector "all" and the vector a[i]. If these numbers are equal, then this substring occurred only in the string s[i] and can be used as a key substring. By changing the base and modulo of the hash, you can pass the WA caused by collision of hashes (I used p = 2313 and mod = 1000000123). The time complexity will be O(max_len * n^2 * log(n)), where max_len is the maximal length of a string.

I use suffix array but WA3.
Give me some tests.

#include <string>
#include <iostream>
using namespace std;

int min(int x, int y) { return x < y ? x : y; }
int max(int x, int y) { return x > y ? x : y; }
int Min(int l, int r);

const int nmax = 1005;
const int maxlen = 1000 * 105;
const int alphabet = 256;

int n, m, sum;
int p[maxlen], cnt[maxlen], c[maxlen];
int pn[maxlen], cn[maxlen], lcp[maxlen];
int who[maxlen], up[maxlen], down[maxlen], a[nmax], b[nmax];
int ans_len[nmax], ans_ind[nmax];
string s, str[nmax];

int main()
{
    cin>>m;
     for(int i=0;i<m;i++) cin>>str[i], s+=str[i];
     m++;
     str[m-1]="#";
     s+=str[m-1];

    n = s.length();

    memset(cnt, 0, alphabet * sizeof(int));
    for (int i = 0; i<n; ++i) ++cnt[s[i]];
    for (int i = 1; i<alphabet; ++i) cnt[i] += cnt[i - 1];
    for (int i = 0; i<n; ++i) p[--cnt[s[i]]] = i;
    c[p[0]] = 0;
    int classes = 1;
    for (int i = 1; i<n; ++i)
    {
        if (s[p[i]] != s[p[i - 1]])  ++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;
        }
        memset(cnt, 0, classes * sizeof(int));
        for (int i = 0; i<n; ++i) ++cnt[c[pn[i]]];
        for (int i = 1; i<classes; ++i) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; --i) p[--cnt[c[pn[i]]]] = pn[i];
        cn[p[0]] = 0;
        classes = 1;
        for (int i = 1; i<n; ++i)
        {
            int mid1 = (p[i] + (1 << h)) % n, mid2 = (p[i - 1] + (1 << h)) % n;
            if (c[p[i]] != c[p[i - 1]] || c[mid1] != c[mid2]) ++classes;
            cn[p[i]] = classes - 1;
        }
        memcpy(c, cn, n * sizeof(int));
    }

    n--, m--, s.erase(n, 1);
    for (int i = 0; i < n; i++) p[i] = p[i + 1];

    sum = 0;
    for (int i = 0; i < m; i++) a[i]=sum, b[i]=sum+str[i].length()-1, sum += str[i].length();

    for (int i = 0; i < n; i++)
    {
        int j = 0;
        while (!(a[j] <= p[i] && p[i] <= b[j])) j++;
        who[i] = j;
    }

    for (int i = 0; i <= n - 2; i++)
    {
        lcp[i] = 0;
        int hr = max(p[i], p[i+1]);
        int gr = min(b[who[i]]-p[i]+1, b[who[i+1]]-p[i+1]+1);
        while (hr+lcp[i]<n && lcp[i]<gr && s[p[i] + lcp[i]] == s[p[i + 1] + lcp[i]]) lcp[i]++;
    }

    down[0] = -1;
    for (int i = 1; i < n; i++) down[i] = who[i - 1] == who[i]? down[i - 1] : i - 1;

    up[n - 1] = -1;
    for (int i = n - 2; i >= 0; i--) up[i] = who[i + 1] == who[i] ? up[i + 1] : i + 1;

    for (int i = 0; i < m; i++) ans_len[i] = str[i].length(), ans_ind[i]=a[i];

    for (int i = 0; i < n; i++)
    {
        int val1 = down[i] == -1 ? 0 : Min(down[i], i - 1);
        int val2 = up[i] == -1 ? 0 : Min(i, up[i]-1);
        int now_len = max(val1, val2) + 1;
        if (now_len<=b[who[i]]-p[i]+1 && ans_len[who[i]] > now_len) ans_len[who[i]] = now_len, ans_ind[who[i]] = p[i];
    }

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < ans_len[i]; j++) cout << s[ans_ind[i] + j];
        if(i+1<m) cout << endl;
    }

    return 0;
}


int Min(int l, int r)
{
     int res=maxlen+5;
     for(int i=l;i<=r;i++) res=min(res, lcp[i]);
     return res;
}

Edited by author 16.08.2018 00:42

If i use hash-table, i get WA. Because due to the small MOD ~10^6, i get probably a coincidence of some hashes.
(I used the degree = 31 and tried modules 1000003,... etc.)

If i use simply linear hash (in common vector) and sorting i get TL.

If i keep hash of each string in separate vectors, and then use a binary search, then again i get TL.

:(

try this test
2
abab
baa


answer:
ab
aa

Please, give me some hints on how to solve it. Thanks in advance.

I was trying to do the following.
Construct suffix automation for each command.
Binary search for length of each key substring.
Binary search works as follows.
For each substring of command of len (lower_bound+upper_bound) /2 check whether it is a substring of another command.

I got WA on test 3 and cant find error on my code despire of using lots of random test. I using suffix array and lcp. Can anyone give me any test to check :(

I'm afraid that i'm getting WA on 7-th test because of hash collisions. How to avoid it? Please, give me some recipes) I tried to change prime base - 31,43,57 - anyway WA#7.

Edited by author 07.11.2010 10:15

On submission 4620967 a have verdict MemoryLimit, but used memory is 8954KB.

I find many solutions are less than 1 second. Could any one give me some hint to improve efficiency. Thanks in advance.

2MB below memory limit =) Long live java
Here some tests i used while debugging

// TEST1
2
xex
dex
===
xe
d

// TEST2
41
fambgpzqrty
sdonrsdraukcyhuqkilkglngf
sopodzkg
bdcmwciyhndeglmlvqbqtthjryyuwgfclhjfip
lbajgfskbozdqmgckgezznkpgugfz
snsocdowvvqdev
jksdqqenkgcqjthjzvojplfnugkdedrkc
iqqpop
ovpdvwfhfvolfxocniggdvjwrmx
sja
cobzqhaucqxswmwllshx
lry
oeiypcukxz
lduqkoliyvcwnnbqugclobhjciikohxfoin
hmz
ojstdjsldeclaleqbfvhsadicrwkgqvzrmjhqhekxgvfd
oufixbnpzoaayonlnslfkacqdjuiawoqfrkihabxgmsvgtcp
ctlzhcmwejtadvuphcaspdvyf
chhpnmm
mrbtinhjnfolghxgdjidodstqkkfqogsbbpktlttghrepxjcol
hfsjtscdjjlfdtfyegqvgteqzqmm
nkrfvuqjahmmpmfazgsubmshituvypamhoj
vksaiuuzs
nbhuymzrmiuinaefhzfm
dmwdvqmxqtiqybbfwf
xeqnhxwfrhilciutjlpfoepaqemvpivkphwszacafleezx
cjttarkxvfv
vbc
agevqmewepvrraktbgn
lcxgjehoqexrenflpdoiptwqeruhtbiijmxrfqbxbxtl
flcrqpdabhztdiykzvkbavrhxephdyhssjmhnrgvhoqzbm
ggriibylnxqibmfpoqdiqjesqrtukvheib
wfe
icftkm
gacivigsalt
xmegpphjequeioughiqpznh
mggtwlqcpdhsvovftb
vsx
fowgljhypolrqzmdzkpthinrvmapvbqhrrmbaodyikuuvnyqcx
vgedqdhomtebcomvvkftuihtaihrubhawrs
rsuahbpehidduujzpajshuugrpmzvd
====
ty
cy
sop
bd
lb
sn
jk
iqq
vw
sja
bz
lry
pc
ko
hmz
ec
uf
ct
ch
mr
ts
kr
uz
uy
dm
qn
cj
vbc
ag
gj
da
ri
fe
cf
ga
xm
lq
vs
lj
om
ua

Edited by author 22.07.2011 16:55