-
Notifications
You must be signed in to change notification settings - Fork 0
/
Distinct substring.cpp
76 lines (70 loc) · 1.22 KB
/
Distinct substring.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
// template by Utkarsh trivedi
// problem id- Disubstr Based on- count of trie nodes (WHICH I USED HERE) or suffix array & lcp calculation
// Total nodes in a trie = number of substring
#include<stdio.h>
#include<string.h>
#define s(x) scanf("%d",&x)
#define p(x) printf("%d",x)
#define nl printf("\n")
typedef long long ll;
struct node
{
char data;
node* child[128];
};
int print(node *t)
{
if(t)
{
p((int)t->data-'0'); printf(" ");
for(int i=0;i<128;i++)
{
if(t->child[i]!=NULL)
{ print(t->child[i]); }
}
}
}
int main()
{
int t,i,j,k,l,m,n;
node *temp;
char str[1002];
s(t);
while(t--)
{
int count=0;
node* root=new node;
root->data=char(1);
temp=root;
memset(&temp->child,0,sizeof(temp->child));
scanf("%s",str); l=strlen(str);
for(i=0;i<l;i++)
{
temp=root;
for(j=i;j<l;j++)
{
k=(int)str[j];
if(temp->child[k]==0)
{
for(m=j;m<l;m++)
{
k=(int)str[m];
temp->child[k]=new node;
count++;
temp->child[k]->data=str[m];
temp=temp->child[k];
memset(&temp->child,0,sizeof(temp->child));
}
break;
}
else
{
temp=temp->child[k];
}
}
}
print(root);
p(count);
nl;
}
}