/*****************************************************************************
* Section 15
* M/c No : M
* Roll No : 18CS100XY
* Names : Anirban Ghose, Soumyajit Dey, Aritra Hazra
* Problem No : LT1-EVEN-2
* Description : Program to find the given prefix in all substrings of a string
******************************************************************************/

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

// checks whether string 'str' occurs anytime in string 'textString[0..index]'
int isUnique(int index, int l, char *textString, char *str)
{
    int i, j, k, counter = 0, n = index;
    char *tempStr = (char*)malloc((index+1)*sizeof(char));
    
    for (i=0; i<n; i++) {
        j = i+l-1;
        counter = 0;
        for (k=i; k<=j; k++) {
            tempStr[counter++]=textString[k];
        }
        if (!strcmp(tempStr,str)) {
            return 0;
        }
    }
    return 1;
}

// checks whether string 'prefixStr' is actually a prefix of 'str'
int isPrefix(char *prefixStr, char *str)
{
    int counter = 0;
    
    while ( prefixStr[counter]!='\0' ) {
        if ( prefixStr[counter]!=str[counter] ) {
            return 0;
        }
        counter++;
    }
    return 1;
}

int main()
{
    int n, m, i, j, k, l, counter, numStr=0;
    char *prefixString, *textString, *tempStr;
    
    /* scanning text string and reporting the corner invalid cases */
    printf("Enter Length of Text String (n): ");
    scanf("%d",&n);
    if (n < 1) {
        printf("Enter a Positive Length. Otherwise, No Text String to Enter!\n");
    }
    else {
        /* scanning prefix string and reporting the corner invalid cases */
        printf("Enter Length of Prefix String (m): ");
        scanf("%d",&m);
        if (m < 1) {
            printf("Enter a Positive Length. Otherwise, No Prefix String to Enter!\n");
            if (m == 0){
                printf("++ There is No Prefix String to Match!\n");
            }
        }
        else {
            /* initializing strings using synamix memory allocation */
            prefixString = (char*)malloc(m*sizeof(char));
            textString = (char*)malloc(n*sizeof(char));
            tempStr = (char*)malloc(n*sizeof(char));
            
            /* scanning text and prefix strings from user input */
            printf("Enter Text String: ");
            scanf("%s", textString);
            printf("Enter Prefix String: ");
            scanf("%s", prefixString);
            
            if (m > n) { /* prefix string is longer than text string */
                printf("++ Number of Prefix Instances Found: 0\n");
            }
            else {
                printf("++ Prefix Matched Substring Instances:");
                /* Generating all substrings */
                for (l=1; l<=n; l++) {
                    /* check only those substrings whose length >= length of prefixString */
                    if ( m <= l ) {
                        for (i=0; i<n-l+1; i++) {
                            j = i+l-1;
                            counter = 0;
                            /* store one string in tempStr */
                            for (k=i; k<=j; k++) {
                                tempStr[counter++]=textString[k];
                            }
                            tempStr[k]='\0';
                            /* check for uniqueness and prefix */
                            if (isUnique(i, l, textString, tempStr)) {
                                if (isPrefix(prefixString, tempStr)) {
                                    printf(" %s,", tempStr);
                                    numStr++;
                                }
                            }
                        }
                    }
                }
                printf("\n");
            }
            printf("++ Number of Prefix Instances Found: %d\n",numStr);
        }
    }
    
    return 0;
}