Finding distinct substrings

Question

pranay_agg 0 Newbie Poster

16 Years Ago

hi, can someone please tell me the approach i should take to find the distinct substrings of a string ?

c++

5 Contributors
12 Replies
543 Views
23 Hours Discussion Span
Latest Post 16 Years Ago Latest Post by mrnutty

Dani AI

Generated 10 Months Ago

Short clarification and where the thread landed: the OP () is asking for the count of distinct, non‑empty contiguous substrings (so "ccccc" -> 5, "ababa" -> 9). Several people suggested brute force generation with containers (, ) and 's 2^n-1 comment is a mismatch — that counts subsets, not contiguous substrings.

Fast summary of options and costs:

Brute force: generate every substring and insert into a set/unordered_set (or use a rolling hash to avoid copying strings). Simple to code but O(n^2) substrings and O(n^2) memory in the worst case; OK for small n. (geeksforgeeks.org)
Suffix array + LCP: build suffix array, compute LCP with Kasai, then
distinct_count = n*(n+1)/2 - sum(LCP). Works in O(n log n) (or O(n) with advanced SA) and O(n) extra memory — good for larger inputs. (cp-algorithms.com)
Suffix automaton (SAM): builds in linear time O(n) (alphabet treated as constant or use maps), uses O(n) states, and the number of distinct non‑empty substrings = sum over states (len[state] - len[link[state]]). Often the simplest O(n) solution in contests. (cp-algorithms.com)

Compact C++ suffix‑automaton example (counts non‑empty distinct substrings):

#include <bits/stdc++.h>
using namespace std;

struct State {
    int len = 0, link = -1;
    unordered_map<char,int> next;
};

long long count_distinct_substrings(const string &s) {
    vector<State> st; st.reserve(s.size()*2);
    st.push_back(State()); // initial
    int last = 0;
    for (char c : s) {
        int cur = st.size(); st.push_back(State());
        st[cur].len = st[last].len + 1;
        int p = last;
        while (p != -1 && !st[p].next.count(c)) {
            st[p].next[c] = cur; p = st[p].link;
        }
        if (p == -1) st[cur].link = 0;
        else {
            int q = st[p].next[c];
            if (st[p].len + 1 == st[q].len) st[cur].link = q;
            else {
                int clone = st.size(); st.push_back(st[q]);
                st[clone].len = st[p].len + 1;
                while (p != -1 && st[p].next[c] == q) {
                    st[p].next[c] = clone; p = st[p].link;
                }
                st[q].link = st[cur].link = clone;
            }
        }
        last = cur;
    }
    long long ans = 0;
    for (int i = 1; i < (int)st.size(); ++i)
        ans += st[i].len - st[st[i].link].len;
    return ans;
}

When to use what: for tiny inputs use the set/rolling‑hash quick solution; for n up to 1e5 prefer SAM or suffix‑array+LCP. If the alphabet is small (e.g. lowercase letters) you can replace maps with fixed arrays for speed.

All 12 Replies

VernonDozier 2,218 Posting Expert

16 Years Ago

The question is too vague. Give us an example of a string and the appropriate substrings for that string.

Ancient Dragon 5,243 Achieved Level 70

16 Years Ago

Do you mean std::string? Yes, then use its find() method. If you mean character array then use standrd C function strstr() which is declared in string.h (or cstring for c++ programs)

Of course you may not be allowed to use either of those if your instructor wants you to write your own function.

Edited 16 Years Ago by Ancient Dragon because: n/a

VernonDozier 2,218 Posting Expert

16 Years Ago

e.g 1
string s = "ccccc"
then ans = 1
e.g 2
s = "abc"
ans = 7

Not sure what you mean. 2 and 7 aren't substrings and they aren't the number of distinct substrings either. I can make more than two substrings from "ccccc". ("c", "cc", "ccc", "cccc"). You're going to have to explain what you are doing and how you got those answers.

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

pranay_agg 0 Newbie Poster · Answer 1 · 2010-03-12T13:57:36+00:00

The question is too vague. Give us an example of a string and the appropriate substrings for that string.

e.g 1
string s = "ccccc"
then ans = 1
e.g 2
s = "abc"
ans = 7

pranay_agg 0 Newbie Poster · Answer 2 · 2010-03-12T17:42:05+00:00

Not sure what you mean. 2 and 7 aren't substrings and they aren't the number of distinct substrings either. I can make more than two substrings from "ccccc". ("c", "cc", "ccc", "cccc"). You're going to have to explain what you are doing and how you got those answers.

sorry it was a mistake
for s = ccccc
no of distinct substrings are 5
and for s = ababa
its 9

pranay_agg 0 Newbie Poster · Answer 3 · 2010-03-12T17:42:23+00:00

Not sure what you mean. 2 and 7 aren't substrings and they aren't the number of distinct substrings either. I can make more than two substrings from "ccccc". ("c", "cc", "ccc", "cccc"). You're going to have to explain what you are doing and how you got those answers.

sorry it was a mistake
for s = ccccc
no of distinct substrings are 5
and for s = ababa
its 9

VernonDozier 2,218 Posting Expert Featured Poster · Answer 4 · 2010-03-12T22:47:29+00:00

So are you looking for an algorithm, looking for code, what? The brute force way would be to set up a vector (or whatever storage you want to use) and generate all substrings one by one. Search the vector (Binary Tree might be better) and if the substring is already there, don't insert. If it isn't there, insert. At the end, you have a tree/vector/whatever of all the substrings.

That's a brute force way. There may be more elegant/efficient methods.

tetron 22 Junior Poster · Answer 5 · 2010-03-12T23:13:14+00:00

you would want two methods:

1st method get all of the sub strings of a length for each input

2nd method find the unique strings of a length

#include <vector>
#include <string>

class sub_string_counter()
{
public:
sub_string_counter();
std::vector<std::string> get_substrs(std::string & from,  int len);
int unique_strings(std::vector<std::string> &vs);
}

the function you need for 1 is .substr() you need the start and length parameters

//pseudo code
std::string input;
//do while start + length <= input.size();
std::string output = input.sub_str(start, length);
vs.push_back(output);

the next stage requires that you find the unique values in the vector

you can test the current string against all of the strings before it in the vector if not found
increase count
else
do nothing

sorry it was a mistake
for s = ccccc
no of distinct substrings are 5
and for s = ababa
its 9

Ancient Dragon 5,243 Achieved Level 70 Team Colleague Featured Poster · Answer 6 · 2010-03-13T02:21:16+00:00

Ancient Dragon 5,243 Achieved Level 70

16 Years Ago

Edited 16 Years Ago by Ancient Dragon because: n/a

mrnutty 761 Senior Poster · Answer 7 · 2010-03-13T02:28:35+00:00

If you don't need to print out the actual permutations, then you can
just calculate the number of different permutation.
Maybe something like this would work :

return  pow(2.0 , double( strlen(str) ) ) - 1;

Ancient Dragon 5,243 Achieved Level 70 Team Colleague Featured Poster · Answer 8 · 2010-03-13T02:35:08+00:00

If you don't need to print out the actual permutations, then you can
just calculate the number of different permutation.
Maybe something like this would work :
return  pow(2.0 , double( strlen(str) ) ) - 1;

I don't think so. In "ccccc" there are only 5, but your formula would product (2^5)-1 = 31.

mrnutty 761 Senior Poster · Answer 9 · 2010-03-13T02:52:02+00:00

I don't think so. In "ccccc" there are only 5, but your formula would product (2^5)-1 = 31.

Oh, wait, should have read the title, he needs only the distinct ones.
I'll try to formulate something.

Finding distinct substrings

Dani AI

Recommended Answers Collapse Answers

All 12 Replies

Recommended Answers