interviewstreet-string similarity - 클래스 스트리밍 프로세스

제목 출처:https://www.interviewstreet.com/challenges/dashboard/#problem/4edb8abd7cacd
문제 해결 보고서:
간단한 문자열 처리로 S의 모든 접두사에 대해 S와 유사도를 계산하고 유사도 계산은 귀속으로 한다.

#include 
#include 
using namespace std;

int getSim(char* str1, char* str2)
{
    if ( *str1 == '\0' || *str2 == '\0')
        return 0;
    if (*str1 != *str2)
        return 0;
    if ( *str1 == *str2)
        return 1 + getSim(str1+1, str2+1);
}

int main()
{
    char * s = new char[100000];
    int N;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int similarity = 0;
        cin >> s;
        similarity += strlen(s);
        for (int i = 1; i < strlen(s); i++)
        {
            similarity += getSim(s, s + i);
        }
        cout << similarity << endl;
    }
}

부록:
String Similarity (25 Points)
For two strings A and B, we define the similarity of the strings to be the length of the longest prefix common to both strings. For example, the similarity of strings "abc"and "abd"is 2, while the similarity of strings "aaa"and "aaab"is 3.
Calculate the sum of similarities of a string S with each of it's suffixes.
Input: The first line contains the number of test cases T. Each of the next T lines contains a string each.
Output: Output T lines containing the answer for the corresponding test case.
Constraints: 1 <= T <= 10 The length of each string is at most 100000 and contains only lower case characters.
Sample Input: 2 ababaa aa
Sample Output: 11 3
Explanation: For the first case, the suffixes of the string are "ababaa", "babaa", "abaa", "baa", "aa"and "a". The similarities of each of these strings with the string "ababaa"are 6,0,3,0,1,1 respectively. Thus the answer is 6 + 0 + 3 + 0 + 1 + 1 = 11.
For the second case, the answer is 2 + 1 = 3.