# HackerEarth Unique Gems problem solution

In this HackerEarth Unique Gems problem solution Rahul has entered into a mysterious land of gems. There is a record S for each of the gems that is maintained in form of a string. Each gem is characterized by some substring of this string. Interestingly, the number of occurrences of a sub-string in S is the exact number of such gems present in the land.

However, Rahul is only interested in unique gems. Please tell the number of such sub-strings that occur exactly once.

## HackerEarth Unique Gems problem solution.

`import java.io.IOException;import java.io.OutputStreamWriter;import java.util.Arrays;import java.io.BufferedWriter;import java.util.InputMismatchException;import java.util.Comparator;import java.io.OutputStream;import java.io.PrintWriter;import java.io.Writer;import java.io.InputStream;public class Main {    public static void main(String[] args) {        InputStream inputStream = System.in;        OutputStream outputStream = System.out;        InReader in = new InReader(inputStream);        OutputWriter out = new OutputWriter(outputStream);        TwoRepetitions solver = new TwoRepetitions();        int testCount = Integer.parseInt(in.next());        for (int i = 1; i <= testCount; i++)            solver.solve(i, in, out);        out.close();    }}class TwoRepetitions {    public void solve(int testNumber, InReader in, OutputWriter out) {        String s = in.readString();        int n = s.length();        int[] sa = SuffixArray.suffixArray(s);        int[] lcp = SuffixArray.lcp(sa, s);        int last = 0;        long ans = 0;        long dis = 1L * n * (n + 1L) / 2;        for (int l : lcp) {            int add = l - last;            if(add > 0) ans += add;            last = l;            dis -= l;        }        out.printLine(dis - ans);    }}class InReader {    private InputStream stream;    private byte[] buf = new byte[1024];    private int curChar;    private int numChars;    private SpaceCharFilter filter;    public InReader(InputStream stream) {        this.stream = stream;    }    public static boolean isWhitespace(int c) {        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;    }    public int read() {        if (numChars == -1)            throw new InputMismatchException();        if (curChar >= numChars) {            curChar = 0;            try {                numChars = stream.read(buf);            } catch (IOException e) {                throw new InputMismatchException();            }            if (numChars <= 0)                return -1;        }        return buf[curChar++];    }    public int readInt() {        int c = read();        while (isSpaceChar(c))            c = read();        int sgn = 1;        if (c == '-') {            sgn = -1;            c = read();        }        int res = 0;        do {            if (c < '0' || c > '9')                throw new InputMismatchException();            res *= 10;            res += c - '0';            c = read();        } while (!isSpaceChar(c));        return res * sgn;    }    public long readLong() {        int c = read();        while (isSpaceChar(c))            c = read();        int sgn = 1;        if (c == '-') {            sgn = -1;            c = read();        }        long res = 0;        do {            if (c < '0' || c > '9')                throw new InputMismatchException();            res *= 10;            res += c - '0';            c = read();        } while (!isSpaceChar(c));        return res * sgn;    }    public String readString() {        int c = read();        while (isSpaceChar(c))            c = read();        StringBuffer res = new StringBuffer();        do {            res.appendCodePoint(c);            c = read();        } while (!isSpaceChar(c));        return res.toString();    }    public boolean isSpaceChar(int c) {        if (filter != null)            return filter.isSpaceChar(c);        return isWhitespace(c);    }    public String next() {        return readString();    }    public interface SpaceCharFilter {        public boolean isSpaceChar(int ch);    }}class OutputWriter {    private final PrintWriter writer;    public OutputWriter(OutputStream outputStream) {        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));    }    public OutputWriter(Writer writer) {        this.writer = new PrintWriter(writer);    }    public void print(Object... objects) {        for (int i = 0; i < objects.length; i++) {            if (i != 0)                writer.print(' ');            writer.print(objects[i]);        }    }    public void printLine(Object... objects) {        print(objects);        writer.println();    }    public void close() {        writer.close();    }}class SuffixArray {    public static int[] suffixArray(final CharSequence str) {        int n = str.length();        Integer[] order = new Integer[n];        for (int i = 0; i < n; i++)            order[i] = n - 1 - i;        Arrays.sort(order, new Comparator<Integer>() {            @Override            public int compare(Integer o1, Integer o2) {                return Character.compare(str.charAt(o1), str.charAt(o2));            }        });        int[] sa = new int[n];        int[] rank = new int[n];        for (int i = 0; i < n; i++) {            sa[i] = order[i];            rank[i] = str.charAt(i);        }        for (int len = 1; len < n; len *= 2) {            int[] r = rank.clone();            for (int i = 0; i < n; i++) {                rank[sa[i]] = i > 0 && r[sa[i - 1]] == r[sa[i]] && sa[i - 1] + len < n && r[sa[i - 1] + len / 2] == r[sa[i] + len / 2] ? rank[sa[i - 1]] : i;            }            int[] cnt = new int[n];            for (int i = 0; i < n; i++)                cnt[i] = i;            int[] s = sa.clone();            for (int i = 0; i < n; i++) {                int s1 = s[i] - len;                if (s1 >= 0)                    sa[cnt[rank[s1]]++] = s1;            }        }        return sa;    }    public static int[] lcp(int[] sa, CharSequence s) {        int n = sa.length;        int[] rank = new int[n];        for (int i = 0; i < n; i++)            rank[sa[i]] = i;        int[] lcp = new int[n - 1];        for (int i = 0, h = 0; i < n; i++) {            if (rank[i] < n - 1) {                int j = sa[rank[i] + 1];                while (Math.max(i, j) + h < s.length() && s.charAt(i + h) == s.charAt(j + h)) {                    ++h;                }                lcp[rank[i]] = h;                if (h > 0)                    --h;            }        }        return lcp;    }}`

### Second solution

`#include <cstdio>#include <cmath>#include <iostream>#include <set>#include <algorithm>#include <vector>#include <map>#include <cassert>#include <string>#include <cstring>#include <queue>using namespace std;#define rep(i,a,b) for(int i = a; i < b; i++)#define S2(x,y) scanf("%d%d",&x,&y)#define P(x) printf("%d\n",x)#define all(v) v.begin(),v.end()#define sz size()#define F first#define S secondtypedef long long int LL;typedef pair<int, int > pii;typedef vector<int > vi;const int N = 100001;string s;vector<pii > ranks;pair<int, pii > v[N];int tag[N][22];int mxPow;int n;void buildSA(string &s) {    n = s.sz;    rep(i,0,n) {        v[i].F = s[i] - 'a' + 1;        v[i].S.F = -1;        v[i].S.S = i;        tag[i][0] = v[i].F;    }    int len = 1;    int j = 0;    while(len < n) {        len += len;        j++;        rep(i,0,n) {            v[i].F = tag[i][j-1];            if(i+len/2 < n) v[i].S.F = tag[i+len/2][j-1];            else v[i].S.F = -1;            v[i].S.S = i;        }        sort(v, v+n);        int tagId = 1;        tag[v[0].S.S][j] = 1;        rep(i,1,n) {            if(v[i].F != v[i-1].F || v[i].S.F != v[i-1].S.F) {                tagId++;            }            tag[v[i].S.S][j] = tagId;        }    }    mxPow = j;}int lcp(int x, int y) {    int res = 0;    for(int i = mxPow; i >= 0; i--) {        if(tag[x][i] == tag[y][i]) {            res += 1 << i;            x += 1 << i;            y += 1 << i;        }        if(x >= n || y >= n) break;    }    return res;}int main() {    int t;    cin >> t;    assert(t >= 1 && t <= 10);    while(t--) {        cin >> s;        buildSA(s);        int n = s.sz;        assert(n > 0 && n <= 100000);        ranks.clear();        rep(i,0,n) {            ranks.push_back(make_pair(tag[i][mxPow], i));        }        sort(all(ranks));        LL ans = 0;        rep(i,0,n) {            int mx = 0;            if(i-1 >= 0) mx = max(mx, lcp(ranks[i-1].S, ranks[i].S));            if(i+1 < n) mx = max(mx, lcp(ranks[i+1].S, ranks[i].S));            // P(mx);            ans += n - ranks[i].S - mx;        }        cout << ans << endl;    }    return 0;}`