Count unique substrings in a string

[Bhaskar Bantupalli]

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());
    }

}

[Campbell Ritchie]

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]

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?

[Campbell Ritchie]

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]

@ 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).

[Bhaskar Bantupalli]

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

[Mike Simmons]

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]

Now, that is a great site! Bookmarked it.

[Mike Simmons]

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.