Mukul
BAN USERUse a suffix array and calculate the longest common prefix for the adjacent strings in the array.
Total no. of substrings = n*(n+1)/2
Now find the sum of all LCP for the suffix array.
No. of distinct substrings = Total no. of substrings - sum of all LCP
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int pstrcmp(const void* p, const void* q)
{
return strcmp(*(const char**)p, *(const char**)q);
}
int lcp(char *p, char *q)
{
int len = 0;
while(*p!='\0' && *p == *q){
len++;
p++;
q++;
}
return len;
}
int main()
{
char s[100];
printf("Enter string:\n");
scanf("%s",&s);
int len;
len = strlen(s);
char *a[len];
//Assign the suffix
for(int i=0;i<len;i++)
a[i] = &s[i];
//Sort the suffix array
qsort(a,len,sizeof(char *),pstrcmp);
int sum = 0;
for(int i = 0;i<len-1;i++){
int l;
l = lcp(a[i],a[i+1]);
sum = sum + l;
}
int res;
res = (len * (len+1))/2;
res = res - sum;
printf("%d\n",res);
return 0;
}
No. You will have to pass the size as a parameter to the function. You can use sizeof to calculate the size of array inside the main function but not when the array is passed to a function as a parameter.
- Mukul October 29, 2012