Forums:

Count unique substrings in a string

Ranch Hand

Posts: 87

posted 7 months ago

Number of slices to send:

Optional 'thank-you' note:

Send

Problem link: Distint Substrings

I tried solving using prefix function based on Prefix function - KMP

but the solution described is O(n^2). And I want to solve it in O(n)

//package cses;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class DistinctSubstrings {
    int[] prefixFunction(char[] s) {
        int n = s.length;
        int[] pf = new int[n];

for(int i=1;i<n;i++) {
            int j = pf[i-1];
            while (j > 0 && s[i] != s[j]) {
                j = pf[j-1];
            }
            if(s[i] == s[j]) j++;
            pf[i] = j;
        }
        return pf;
    }
    void run() {
        String t = next();
        long res = 0;
        for(int i=0;i<t.length();i++){
            String s = t.substring(0, i+1);
            int n = s.length();
            int[] pf = prefixFunction(reverse(s.toCharArray()));
            res += n - (Arrays.stream(pf).reduce(0, Integer::max));

}

out.println(res);
        out.close();
    }
    char[] reverse(char[] arr) {
        for(int i=0, j=arr.length-1;i<j;i++, j--) {
            char tmp = arr[i];
            arr[i] = arr[j];
            arr[j]= tmp;
        }
        return arr;
    }

public static void main(String[] args) {
        DistinctSubstrings ob = new DistinctSubstrings();
        ob.run();
    }
    // ------------------

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    PrintWriter out = new PrintWriter(System.out);

String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

int nextInt() {
        return Integer.parseInt(next());
    }

long nextLong() {
        return Long.parseLong(next());
    }

double nextDouble() {
        return Double.parseDouble(next());
    }

}

Bhaskar Bantupalli

Campbell Ritchie

Marshal

Posts: 79392

377

posted 7 months ago

Number of slices to send:

Optional 'thank-you' note:

Send

Why are you using StringTokenizer, and InputStreamReader, which are regarded as legacy code?

I think you may get more attention if I add you to one of our other fora.

Bhaskar Bantupalli

Ranch Hand

Posts: 87

I like...

posted 7 months ago

Number of slices to send:

Optional 'thank-you' note:

Send

Why are you using StringTokenizer, and InputStreamReader, which are regarded as legacy code?

I have been using a template for online problem solving. I haven't changed it in years. Which API do you recommend that works for java 8 and 8+ alike

I think you may get more attention if I add you to one of our other fora.

Please add me. Can you say what the other forum is?

Bhaskar Bantupalli

Campbell Ritchie

Marshal

Posts: 79392

377

posted 7 months ago

Number of slices to send:

Optional 'thank-you' note:

Send

Can you envisage an algorithm running in linear time?

Bhaskar Bantupalli wrote:. . . . Which API do you recommend that works for java 8 and 8+ alike

I would use a Scanner to read System.in. It does its own tokenising which makes it unnecessary to use the tokeniser. It also provides methods like nextInt() which make it unnecessary to use Integer.parseInt() or similar.
For other input, use a Path object, as described in the Java™ Tutorials.

. . . Can you say what the other forum is?

Java in General.

Piet Souris

Bartender

Posts: 5469

212

posted 7 months ago

Number of slices to send:

Optional 'thank-you' note:

Send

@ Bhaskar,

have you read or heard somewhere that an O(N) solution is possible? The ones I found on the internet are all O(N^2).

There are three kinds of actuaries: those who can count, and those who can't.

Bhaskar Bantupalli

Ranch Hand

Posts: 87

I like...

posted 7 months ago

Number of slices to send:

Optional 'thank-you' note:

Send

have you read or heard somewhere that an O(N) solution is possible?

- yes
Based on the time limits and input limits on the problem, the problem if solved cannot be O(n^2). and based on below solutions which I didn't understand much, I thought it is O(n)
https://github.com/Jonathan-Uy/CSES-Solutions/blob/main/String%20Algorithms/Distinct%20Substrings.cpp
https://codeforces.com/blog/entry/95004 - 12th solution and code

Bhaskar Bantupalli

Mike Simmons

Master Rancher

Posts: 4905

posted 7 months ago

Number of slices to send:

Optional 'thank-you' note:

Send

Yes, it looks like there is an O(N) solution to this problem using Suffix Automaton. I'm not sure if there are any other algorithms that solve the problem as efficiently.

Piet Souris

Bartender

Posts: 5469

212

posted 7 months ago

Number of slices to send:

Optional 'thank-you' note:

Send

Now, that is a great site! Bookmarked it.

There are three kinds of actuaries: those who can count, and those who can't.

Mike Simmons

Master Rancher

Posts: 4905

posted 7 months ago

Number of slices to send:

Optional 'thank-you' note:

Send

Agreed - I hadn't seen it before, but found it in Bhaskar's first post above. When another post mentioned suffix automaton, I searched in cp-algorithms.com because that was the resource Bhaskar was using... and there it was.

With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.