class trieNode{
public:
trieNode **children;
trieNode()
{
children = new trieNode*[26];
for(int i=0;i<26;i++)
children[i] = NULL;
}
};
void insert(trieNode *head,string st)
{
int l = st.length();
trieNode *curr = head;
for(int i=l-1;i>=0;i--)
{
int k = st[i] - 'a';
if(curr->children[k] == NULL)
{
curr->children[k] = new trieNode();
}
curr = curr->children[k];
}
}
int countNode(trieNode *head)
{
if(head == NULL)
return 0;
int sum = 0;
for(int i=0;i<26;i++)
{
if(head->children[i] != NULL)
sum += countNode(head->children[i]);
}
return sum+1;
}
int countDistinctSubstring(string s)
{
trieNode *head = new trieNode();
int l = s.length();
for(int i=0;i<l;i++)
{
string sk = s.substr(0,i+1);
//cout<<sk<<endl;
insert(head,sk);
}
int res = countNode(head);
return res;
}