Interviewstreet String Similarity Solution C++

Interviewstreet String Similarity Challenge

Problem Statement

String similarity of two strings is defined as length of longest prefix common to both strings. For example string similarity for abcd and abb is 2, length of ab. Calculate sum of similarities of a string with each of its suffixes.
Input: First line contains T, no of test cases and next T lines contain strings
Output: T lines contain answer.
Sample Input:                                                  Sample Output:
1                                                                       3
aa

Algorithm

1) calculate similarity value of string with each of its suffix, i.e if character at index i matches with 1st character calculate the similarity value for this suffix.
2) For calculating similarity value, start counter with 0 and keep counting until prefix of the given suffix matches with original string. if doesn't match break and return count.
3) Keep calculating sum by adding every count value returned.

If you have a different approach in mind, please share it in comments section.

Solution

#include<stdio.h>
#include<string.h>

int getSimilarity(char str[],int sub_ind,int st);

int main()
{
    int T,len=0,sum=0,i=0;
    char s[100001];
    scanf("%d",&T);
    while(T--)
    {
        sum=0;
        scanf("%s",s);
        int y=strlen(s);
        for(i=0;i<y;i++)
            if(s[i]==s[0])
            {
               
                sum=sum+getSimilarity(s,i,y);
            }
        printf("%d\n",sum);
    }
}

int getSimilarity(char str[],int sub_ind,int st)
{
    int g=sub_ind;
    int j, i=0;
    int count=0;
    for(i=g,j=0;i<st;i++)
        if(str[i]==str[j++])
        {
            count++;
        }
        else
            break;
    return count;  
}

Time Complexity
O(n*n), bcoz if first character of suffix matches with first character of original string then we calculate string similarity for this suffix with original string which takes O(n) time and there can be n such suffix matches.