I tried this approach with Java: Test 5. TL
With C++: Test 9. TL

And seems like this is not enough, however time complexity is O(αk^2 + α|S|*k) where α is hash map hidden constant.

So... did anyone managed to solve it this way?

Try std::unordered_map instead of std::map. This one helped me

how to solve this problem?
construct suffix tree for N times and then LCP or there is easier and faster way?

Is it possible to solve this problem using suffix automata? I got TL5.
But I think that O(N * K) solution have to work faster. Am I wrong? Thanks.

PS. Got AC with KMP O(N * K).

Edited by author 26.08.2015 00:30

finally I solved this using DC3 algorithm (a linear suffix array construction algoritm). it's supposed to run in O(n) time. my java solution runs in ~1.17 but my main language is scala and in scala (the escat same algorithm) is above 2 sec.
is it possible to solve this with KMP faster? i couldn't find a correct solution.

aabaaab => { 0 1 0 1 2 3 }
a 0
aa 1
aab 0
aaba 1
aabaa 2
aabaab 3

6
abcabcabcf
15 15 15 15 18 19 18 18 19 18

Hi,
 Please let me know the input for Test#2.
 I have verified my program with different test cases and is working fine.
 It would be interesting to see which test case is failing.

Could anyone tell me how to solve this task using suffix automata??

try
6
lmffwmnrocz

19 19 20 21 21 21 21 21 21 20 20

I naively applied suffix arrays with lcp and got AC in ~2.7s. (complexity N*K*log^2(K))

But I see that there are submissions with times <0.1s. What are the more efficient algorithms?

Someone mentioned suffix-function - any referece for that?
Also it was said that KMP can be used - can anyone explain how exactly it is applicable here?

Thanks in advance.

I don't know whay this system returnes "wrong answer" !!!
I ran my program several times,both in windows console and Netbeans IDE and every time i got the expected result.
but here neither sending source file nor pasting source code doesnt accept !

and here is the code,if anyone interested :

/*
 * this class implements the encoding requested in problem #1706
 */
/**
 * @author Esmaeil Ashrafi <s.ashrafi@gmail.com>
 */
import java.util.ArrayList;

public class StierlitzCipher {

    private static String input; // the string suppose to be ciphered
    private static int k;        // the length of sub strings
// temporary variable for query substrings
    private static StringBuffer temp = new StringBuffer();
// an array to store substrings of each query string
    private static ArrayList<String> sub = new ArrayList<String>();

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        /* if ran in command line console,first argument willl be the
         * string to cipher and second considered as the key
         */
        if (args.length == 2) {
            input = new String(args[1]);
            k = Integer.parseInt(args[0]);
        } // otherwise use of default values of problem
        else {
            input = new String("abaccc");
            k = 3;
            // prompt the user to using default values
            System.out.println("doing encrypt by default values:"
                    + "\nString : \"abaccc\"\nKey : 3");
        }
        query(input, k);
        System.out.println(); // just for trimming the output !
    }//end of main

    /**
     * gets the entire string and splits it to substrings in length
     * of "len" and sends each substring to method compute
     * for calculating the number of different non-empty substrings
     * could obtained from them.there will be substrings(and
     * consequent call to compute method)call as much as the length
     * of parameter str
     * @param str - the string to be cipher
     * @param len - the length of substrings(the key)
     */
    private static void query(String str, int len) {
        int m, strLen = str.length();
        for (m = 0; m <= strLen - len; m++) {
            compute(str.substring(m, m + len));
        }
        for (m = m; m < strLen; m++) {
            compute(str.substring(m).concat(str.substring(0, len - (strLen - m))));
        }
    }//end of query

    /**
     * queries queryString to calculate number of its different and
     * non-empty substrings and prints the count to the standard output
     * @param queryStr - the string to be queried
     */
    private static void compute(String queryStr) {
        int qLen = queryStr.length();
        for (int i = 0; i < qLen; i++) {
            for (int j = i + 1; j <= qLen; j++) {
                if (!sub.contains(temp.replace(
                        0, temp.length(), queryStr.substring(i, j)).toString())) {
                    sub.add(temp.toString());
                }
            }
        }
        System.out.print(" "+sub.size());
        sub.clear();
    }//end of compute
}//end of class

Edited by author 31.03.2010 05:29

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string a;
int k;
int array[9096], n, bucket[9096], lbucket[9096], h = 0;
void scan(){
    cin >> k >> a;
    a += a.substr(0, k - 1);
    n = a.size();
}
bool f(int x, int y){
    if ( !h )
        return a[x] < a[y];
    if ( bucket[x] < bucket[y] ) return 1;
    if ( bucket[y] < bucket[x] ) return 0;
    int bx, by;
    if ( x + h >= n ) bx = n - (x + h) - 1;
    else bx = bucket[x + h];
    if ( y + h >= n ) by = n - (y + h) - 1;
    else by = bucket[y + h];
    return bx < by;
}
bool makebuckets(){
    int br = 0;
    for ( int i = 0; i < n; ++i ){
        if ( i > 0 )
            if ( f(array[i], array[i - 1]) || f(array[i - 1], array[i]) )
                ++br;
        lbucket[array[i]] = br;
    }
    for ( int i = 0; i < n; ++i )
        bucket[i] = lbucket[i];
    ++br;
    return (br == n);
}
void buildsuffixarray(){
    for ( int i = 0; i < n; ++i )
        array[i] = i;
    sort (array, array + n, f);
    if ( makebuckets() ) return;
    for ( h = 1;; h *= 2 ){
        sort(array, array + n, f);
        if ( makebuckets() ) break;
    }
}
int findnext(int st, int i){
    ++i;
    for (i; i < n; ++i)
        if ( array[i] >= st && array[i] < st + k ) return i;
    return -1;
}
int rez(int t){
    int p = findnext(t, -1), d, result = (k + 1) * k / 2;
    d = findnext(t, p);
    int br = 0;
    while ( d > 0 ){
        int j = 0;
        while ( a[array[p] + j] == a[array[d] + j] && array[p] + j < t + k && array[d] + j < t + k ) ++j;
        result -= j;
        p = d;
        d = findnext(t, d);
        ++br;
    }
    if ( br != k - 1 ) while(1);
    return result;
}
void solve(){
    buildsuffixarray();
    cout << rez(0);
    for ( int i = 1; i < n - k + 1; ++i )
        cout << " " << rez(i);
    cout << endl;
}
int main(){
    scan();
    solve();
}

I am getting mad... no idea where my code is wrong... The idea is right

please give me information of the test 2 of this problem.