PATTERN MATCHING

[0mehedihasan]

https://www.camscanner.com/share/show?device_id=AD_AID-7D9B830855E0CB80&sid=CC4A3311745D436ByY9KL93K&pid=dsa&style=1&t=1674492397&share_link_style=2

[0mehedihasan]

https://drive.google.com/file/d/1c_T9jfuVXVYGJYVRQhG9UcKymHZ3_bcu/view?usp=drivesdk

[0mehedihasan]

Uploading DLD_LAB_MANUAL.pdf…

[razitzanin]

Second Pattern Matching:
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
void compute(char* pat, int M, int* lps);
void secondpattern(char* pat,char* txt)
{
int M = strlen(pat);
int N = strlen(txt);
int lps[M];
compute(pat, M, lps);

int i = 0;
int j = 0;
while ((N - i) >= (M - j))//O(N)
{
    if (pat[j] == txt[i])
    {
        j++;
        i++;
    }

    if (j == M)
    {
        printf("Found pattern at index %d \n", i - j);
        j = lps[j - 1];
    }
    else if (i < N && pat[j] != txt[i])
    {
        if (j != 0)
            j = lps[j - 1];
        else
            i = i + 1;
    }
}

}
void compute(char* pat, int M, int* lps)
{
int len=0;
lps[0]=0;
int i=1;
while(i<M)
{
if (pat[i] == pat[len])
{
len++;
lps[i] = len;
i++;
}
else
{
if (len != 0)
{
len = lps[len - 1];
}
else
{
lps[i] = 0;
i++;
}
}
}
}
int main()
{
char txt[] = "ABABDABACDABABCABABABABCABABABABCABAB";
char pat[] = "ABABCABAB";
secondpattern(pat, txt);
return 0;
}