knuth pattern matching

-

 

#include <stdio.h>
#include <string.h>
int lps[100];
void longestPrefixSuffix(char p[])
{
    int i = 1, j = 0;
    int m = strlen(p);
    lps[0] = 0;
    while (i < m)
    {
        if (p[i] == p[j])
        {
            lps[i] = j + 1;
            i++; j++;
        } else if (j > 0)
        {
            j = lps[j - 1];
        } else {
            lps[i] = 0;
            i++;
        }
    }
}
int kmp(char p[], char t[]) {
    int n = strlen(t), m = strlen(p);
    longestPrefixSuffix(p);
    int i = 0, j = 0;
    while (i < n)
    {
        if (p[j] == t[i])
        {
            if (j == m - 1)
                return i - j;  
            i++; j++;
        } else if (j > 0)
        {
            j = lps[j - 1];
        } else {
            i++;
        }
    }
    return -1;
}
int main()
{
    char text[200], pattern[100];
    printf("Enter the text: ");
    fgets(text, sizeof(text), stdin);
    text[strcspn(text, "\n")] = 0;
    printf("Enter the pattern: ");
    fgets(pattern, sizeof(pattern), stdin);
    pattern[strcspn(pattern, "\n")] = 0;
    int pos = kmp(pattern, text);
    if (pos != -1)
        printf("Pattern found at position %d\n", pos);
    else
        printf("Pattern not found\n");
}

Comments

Post a Comment

Popular posts from this blog

SINGLE LINKED LIST by smd

-
#include <stdio.h> #include <stdlib.h> int count = 0; struct node {       int data;       struct node *next; }  *head = NULL, *newnode, *trav; void create_list() {       int value;       struct node *temp;       newnode = (struct node *)malloc(sizeof(struct node));       printf("Enter the value to be inserted: ");       scanf("%d", &value);       newnode->data = value;       newnode->next = NULL;       if (head == NULL) {           head = newnode;       } else {           temp = head;           while (temp->next != NULL)               temp = temp->next;           temp->next = newnode;       }       count++; } void insert_at_beg...
Read more

BANKING SYSYTEM DATABASE WITH RECORDS

-
Creation of the Database              RED COLOUR : DEFALUT COMMAND   mysql> create database 05D8;                                     GREEN COLOUR : OUTPUT Query OK, 1 row affected (0.12 sec) useing if the database mysql> use 05D8; Database changed CREATING THE TABLE mysql> CREATE TABLE Bank(Bank_ID varchar(20) primary key,Bank_Name VARCHAR(255),Bank_Address VARCHAR(255),Bank_Phone VARCHAR(15)); Query OK, 0 rows affected (0.58 sec) mysql> CREATE TABLE Branch(Branch_ID varchar(25) PRIMARY KEY,Branch_Name VARCHAR(255),Branch_Address VARCHAR(255),Branch_Phone VARCHAR(15),Bank_ID varchar(25),FOREIGN KEY(Bank_ID)REFERENCES Bank(Bank_id)); Query OK, 0 rows affected (0.80 sec) ad more mysql> CREATE TABLE Customer(Customer_ID varchar(25...
Read more

CLL by smd

-
PROGRAM #include <stdio.h> #include <stdlib.h> int count = 0; struct node {  int data; struct node *next; }; struct node *head = NULL, *newnode, *temp; void create_circle_linked_list(); void insert_at_begin(); void insert_at_end(); void insert_at_specific_point(); void delete_at_begin(); void delete_at_end(); void delete_at_specific_point(); void display(); void create_circle_linked_list()  {  int value; printf("Enter the value to be inserted: "); scanf("%d", &value); newnode = (struct node*)malloc(sizeof(struct node)); newnode->data = value; if (head == NULL)  {  head = newnode;  newnode->next = head;  } else  {  temp = head;  while (temp->next != head) temp = temp->next; temp->next = newnode; newnode->next = head;     }     count++; } void insert_at_begin()  { int value;  printf("Enter the value to be inserted: "); scanf("%d", &value); newnode = (struct node*)malloc(si...
Read more