여비의 블로그

/***************************************
일단 recursion으로 풀었음.
2차원 배열을 만들어서 다이나믹프로그래밍으로 바꾸면
좀더 빨라질 것같음.
***************************************/


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

#define MAX 100
char str[2][MAX];
char substr[MAX];

int func(int stNum,int x, int y)
{
        int i;
        if(x<y||str[stNum][x]!=substr[y])
        {
                return 0;
        }
        else
        {
                if(y==0 )
                {
                         return 1;
                }

                else
                {
                        int result=0;
                        for(i=x-1;i>=0;i--)
                        {
                                if(str[(stNum+1)%2][i]==substr[y-1])
                                        result+=func((stNum+1)%2,i,y-1);
                        }
                        return result;
                }
        }
}


int main(int argc, char *argv[])
{
        int result=0;
        int i,j;
        int strlength;
        int sublength;

        printf("string1 : ");
        scanf("%s",str[0]);

        printf("string2 : ");
        scanf("%s",str[1]);

        printf("sub string : ");
        scanf("%s",substr);

        strlength=(int)strlen(str[0]);
        sublength=(int)strlen(substr);


        for(i=0;i<strlength;i++)
        {
                result+=func(0,i,sublength-1)+func(1,i,sublength-1);
        }
        printf("%d
", result);

        return 0;
}