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

include

include

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; }