Saturday 9 January 2016

Find The Location of Sub-string By Using Pattern Matching Table. (Algorithm 3.4)


Before seeing the solution make sure that you tried enough. Don’t paste the whole code, just find out the logic. If you stuck in trouble, just inform me on comment.

/**Bismillahir Rahmanir Rahim.**/

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

char T[10000];
char P[100];
int save = 0, ara[125], TABLE[100][125];
int i, j, k, l, lnth, cndtn, cnt, m;
int F(int s, char t);

int main()
{
    int lnth_p, K, S=0;
    printf("Please, Input String.\n");
    gets(T);
    printf("Please, Input Sub-string.\n");
    gets(P);
    lnth_p = strlen(P);
    for(K=0;T[K]  && S!=lnth_p; K++)
        S = F(S,T[K]);
    if(S == lnth_p) printf("INDEX is started from place %d\n", K-lnth_p);
    else printf("There is no matching\n");
    return 0;
}
int F(int s, char t)
{
    if(save == 0)
    {
        lnth = strlen(P);
        for(i=0; T[i]; i++) ara[T[i]]=1;
        for(i=0; i<lnth; i++)
        {
            for(j=0; j<125; j++)
            {
                if(ara[j]==0) continue;
                if(P[i]==j)
                {
                    TABLE[i][j] = (save+=1);
                    continue;
                }
                for(k=i-1; k>=0; k--)
                {
                    if(P[k] == j)
                    {
                        for(l=k-1,m=i-1, cnt=1; l>=0; l--, m--)
                        {
                            if(P[l] == P[m]) cnt++;
                            else break;
                        }
                        if(cnt == k+1)
                        {
                            TABLE[i][j] = cnt;
                            break;
                        }
                    }
                }

            }
        }
        save = 1;
    }
    return TABLE[s][t];
}

0 comments:

Post a Comment

Note: only a member of this blog may post a comment.