Give me some tests,  please

Edited by author 11.11.2008 23:43

Please give me some tests!

#include <bits/stdc++.h>

using namespace std;

int main()
{
    map<string, int> d;
    string s;
    cin >> s;
    string c = "";
    int n = s.size();
    for (int i = 0; i < n; i++)
    {
        c = s[i];
        d[c]++;
        for (int j = i + 1; j < n; j++)
        {
            c += s[j];
            d[c]++;
        }
    }
    cout << d.size();
}

Remove this comment it contains solution to the problem via z-function.
http://acm.timus.ru/forum/thread.aspx?id=41561&upd=636936488140008501

There were rumors that it is hard to get AC with hashes.
Got AC in 0.031 using standard N log^2 N suffix array. Hashes modulo 2^64 (so there is no explicit divisions in code).
There are couple of tricks, but they all are very easy to code.

1) gethash(i + l, i + mid) == gethash(j + l, j + mid)
&& memcmp(s + i + l, s + j + l, mid - l) == 0
instead of just
gethash(i, i + mid) == gethash(j, j + mid)
in binary search (lcp computing)

2) std::::stable_sort is preferable over std::sort when comparisons are heavy. std::stable_sort makes more assignments in average, but much less comparisons.

0.031 sec, 62 lines of code (including 10 empty, "return 0", 4 includes and so on).

String s = scanner.next();
        TreeSet<String> c = new TreeSet<String>();
        for (int i=0; i<s.length(); i++) {
            c.add(s.substring(i));
        }
        int L = c.size() + 1;
        long total = L - c.first().length();
        while(c.size()>1) {
            String first = c.pollFirst();
            String second = c.first();
            int lcp = LCP(first, second);
            total+= L - second.length() - LCP(first, second);;
        }
        System.out.println(total);

               TIME     Memory
Suffix array - 0.031 s  534 kb
Z-function   - 0.187 s  132 kb

Edited by author 03.12.2014 15:29

Well, the N is rather small that we can construct the suffix array for O(N^2logN)
for example, we get all the suffix and sort it:
a
aa
aaa

then calculate the longest common prefix(LCP) between two neighbour string
we get :
1
2
it means that: the substring "a" occurs 3 times (in string 1,2, LCP is "a",in string 2,3, LCP is "aa", which also contains "a") , and should be counted as once
the substring "aa" occurs twice and it's also should be counted as once
then the answer should be : 3 * (3 + 1) / 2 - 1 - 2 = 3

Please give me some tests.

Well, it's crazy one =)

Let's solve this problem just like classical prefix-function solution, but let's get prefix-func from Z-function instead of using KMP. Here is a part of my code.


        z[0]=0;
        l=r=m=0;
        for(int i=1;i<n;i++)
        {
            if(i<r)
                z[i]=min(z[i-l],r-i+1);
            else
                z[i]=0;
            while(i+z[i]<n && t[i+z[i]]==t[z[i]])z[i]++;
            if(i+z[i]-1>r)
                l=i,r=i+z[i]-1;
        }
        fill(p,p+n,0);
        for(int i=0;i<n;i++)
            for(int j=0;j<z[i] && !p[i-j];j++)
                p[i-j]=z[i]-j;

Help me... I really don't know, why 25000000 TL?
I think 25000000 not many time...and must get AC in 1 sec.

Edited by author 17.04.2008 08:16

Finally got accepted

Some new tricky tests were added. 53 authors lost their AC.

I got AC with prefix function.


Edited by author 06.05.2012 12:56

Can we solve this problems with hashes?
It takes TLE #3 with hash table...
Who solved with hashes, comment please =)

Can anyone solve this task with hash?

Edited by author 06.07.2011 10:45

I know that suffix trees can be used for such problem. How about using a large hash table for storing codes of substrings that we already have? Anyone got AC in that way?

Is empty string is a substring of the whole string?
Is whole string is a substring of the whole string?