Definition: The study of how the data is collected and stored in the memory, how efficiently the data is organized in the memory, how efficiently the data can be retrieved and manipulated, and the possible ways in which different data items are logically or mathematically related is called data structures. �

A data structure is a Specific way to store and organize data in a computer's memory so that these data can be used efficiently later.

​

Data may be arranged in many different ways such as the logical or mathematical model ,a particular organization of data is termed as a data structure.

Classification of Data Structure

​

​

�

Data structure operations

​

Creating: The process of repeatedly adding various data items into the list is called

creating a list �

Inserting: The process of adding a data item into the list is called inserting. �

Deleting: The process of removing a data item from a list is called deleting.

​

Searching: The process of informing whether a particular item is present in a list

or it is not present in a list is called searching. �

Sorting: The process of arranging various data items either in ascending order or

descending order is called sorting. �

Merging: Given two sorted lists we can combine those two lists into a single

sorted list. �

Traversing: The process of accessing each data item exactly once so that it can be

processed and manipulated is called traversal. �

​

POINTERS

When a variable is declared, a specific block of memory within the computer is allocated to hold the value of that variable.

The size of the allocated block depends on the data type.

Consider the following statement.�int x = 10;

Lvalue=Rvalue

printf(“%d %d %d”,x,sizeof(x),&x)

​

The compiler reserves memory for the integer variable x and stores the rvalue 10 in it.

x refers to the value stored at the memory location set aside for x, in this case 10

​

A pointer is a variable that stores the memory location of another variable.

A pointer is a variable that represents the location of a data item, such as a variable or an array element.

Applications of Pointers include ( Not Limited to):�Pointers are used to pass information back and forth between functions.� Pointers enable the programmers to return multiple data items from a function via function arguments.� Pointers provide an alternate way to access the individual elements of an array.� Pointers are used to pass arrays and strings as function arguments. � Pointers are used to create complex data structures, such as trees, linked lists, linked stacks, linked queues, and graphs.�Pointers are used for the dynamic memory allocation of a variable.

General Syntax

data_type *ptr_variable_name;

​

int *pnum;�char *pch;�float *pfnum; ��

�

int x= 10;�int *ptr;�ptr = &x;

​

The * informs the compiler that ptr is a pointer variable and the int specifies that it will store the address of an integer variable.

X Name of the variable

ptr Name of the pointer variable

ptr = &x; ptr is assigned address of variable x

y = *ptr; y is assigned a value of content of the address pointed by ptr

#include <stdio.h>�int main()�{�int num, *pnum;�pnum = &num; �printf("\n Enter the number : ");�scanf("%d", &num);�printf("\n The number that was entered is : %d\n", *pnum);

printf("\n The number that was entered is : %d\n", num);

printf("\n The address is : %u", pnum);

return 0;�} �

What is the expected output?

​

The number that was entered is :

The number that was entered is :

The address is :

​

* pnum Pointer de-referencing

Pointer referencing

int num1 = 2, num2 = 3, sum = 0, mul = 0, div = 1;�int *ptr1, *ptr2;�ptr1 = &num1;�ptr2 = &num2;�sum = *ptr1 + *ptr2;�mul = sum * (*ptr1);�*ptr2 += 1;�div = 9 + (*ptr1)/(*ptr2) – 30;

​

Valid pointer operations

Addition

Subtraction

Comparing pointer (relational Operations)

Multiplication ( not widely used)

​

No division operation are possible

++,--- are valid operations

void *ptr = NULL; Represents null pointer �

Relation between array and pointers

# include <stdio.h>�int main( )�{�int i = 3 ;�printf ( "Address of i = %u\n", &i ) ;�printf ( "Value of i = %d\n", i ) ;�printf ( "Value of i = %d\n", *( &i ) ) ;�return 0 ;�} �

‘*’, called ‘value at address (pointer de-referencing)

Assume the address

What is the program output?

• (*&) complement in informal representation
• Hence it is as good as writing i

dereference operator (*) is used to access the value stored at that address.

Example

Consider the declaration: int x[5] = {1, 2, 3, 4, 5};

Suppose that each integer requires 4 bytes

Compiler allocates a contiguous storage of size 5x4 = 20 bytes

Assume the starting address of that storage is 2500 Element Value Address:

Compiler allocates sufficient amount of storage to contain all the elements of the array in contiguous memory location

base address is the location of the first element (index 0, x[0] in above table) of the array

such as in above table 2500

The array name as a constant pointer to the first element

Both x and &x[0] have the value 2500

int *p is declared and if we define

p = x;

Or

p = &x[0]; they are equivalent

If we increment with p++ then p=&x[1]

Int x[5]={5,6,7,8};

Int i ;

​

For(i=0;i<5;i++)

printf(“%d”,x[i]);

Int x[5]={5,6,7,8};

Int *p,i;

p=x;

For(i=0;i<5;i++)

printf(“%d”,*(p+i));

Pointer to Function

A function pointer is a pointer that stores the address of a function instead of a variable. It allows functions to be called indirectly and passed as arguments to other functions.

#include <stdio.h>

int add(int a, int b)

{

return a + b;

}

int main() {

int (*fptr)(int, int);

​

// Assign address of add()

fptr = &add;

​

// Call the function via ptr

printf("%d", fptr(10, 5));

​

return 0;

}

#include <stdio.h>

int main() {

int var = 10;

void *q;

// Pointer to int

int *ptr1 = &var;

// Pointer to pointer (double pointer)

int **ptr2 = &ptr1;

​

// Accessing values using all three

printf("var: %d\n", var);

printf("*ptr1: %d\n", *ptr1);

printf("**ptr2: %d", **ptr2);

return 0;

}

int myNumbers[4] = {25,50,75,100};�int *p = myNumbers; �printf("%d\n", *p);       �printf("%d\n", *(p + 1)); �printf("%d\n", *(p + 2));

printf("%d\n", *(p++);

//printf("%d\n", *(p + 3));

printf("%d\n", *(p--);

int myNum = 10;       �int *ptr = &myNum;   

int **pptr = &ptr;   

​

printf("myNum = %d\n", myNum);�printf("*ptr = %d\n", *ptr);�printf("**pptr = %d\n", **pptr);

#include <stdio.h>

void swap(int* a, int* b)

{

int temp = *a;

*a = *b;

*b = temp;

}

int main(void)

{

int n1 = 5;

int n2 = 10;

swap(&n1, &n2);

printf(" After swapping :

is %d and n2 is %d\n", n1, n2);

return 0;

}

#include <stdio.h>

float add(int a, int b){ return a + b; }

float subtract(int a, int b){ return a - b; }

float multiply(int a, int b){ return a * b; }

float divide(int a, int b){ return a / b; }

​

int main()

{

float

(*ptr[])(int, int) = {add, subtract, multiply, divide}; int a = 15, b = 10;

// 1 for addition, 2 for subtraction

// 3 for multiplication, 4 for division

int op = 3;

if (op > 5) return 0;

printf("Result: %.2f", (*ptr[op-1])(a, b));

return 0;

}

Dynamic Memory Management

�

free memory region is called heap

#include <stdio.h>

#include <stdlib.h>

void main()

{

int i,n;

int *ptr;

printf("Enter the number of elements\n");

scanf("%d",&n);

ptr = (int *) malloc (sizeof(int)* n);

/* If sufficient memory is not allocated */

if (ptr == NULL)

{ printf("Insuffient memory\n"); return; }

/* Read N elements */

printf("Enter N elements\n"); Enter N elements

for (i = 0; i < n; i++)

scanf("%d", ptr+i);

printf("The given elements are\n");

for (i = 0; i < n; i++)

printf("%d ", *(ptr+i));

#include <stdio.h>�#include <stdlib.h>�int main ()�{�int i,n;�int *arr;�printf ("\n Enter the number of elements: ");�scanf("%d",&n);�arr = (int*) calloc(n,sizeof(int));�if (arr==NULL) exit (1);�printf("\n Enter the %d values to be stored in the array", n);�for (i = 0; i < n; i++)�scanf ("%d",&arr[i]);�printf ("\n You have entered: ");�for(i = 0; i < n; i++)�printf ("%d",arr[i]);�free(arr);�return 0; }

enter value of m and n3 3

1 2 3

1 2 3

1 2 3

1 2 3

1 2 3

1 2 3

603433696 603433700 603433704

603433728 603433732 603433736

603433760 603433764 603433768

-527815968 -527815964 -527815960

-527815936 -527815932 -527815928

-527815904 -527815900 -527815896

#include<stdio.h>

// Dynamic array using pointer

Void main()

{

int i,n,*p;

printf(“enter number of elements in an array”);

scanf(“%d”,&n);

for(i=0;i<n;i++)

scanf(“%d”,(p+i));

for(i=0;i<n;i++)

printf(“%u=%d”,(p+i),*(p+i));

}

​

Output

Enter number of elements in an array 5

1 2 3 4 5

1212=1

1214=2

1216=3

1218=4

1220=5

void main()

{

char *str;

str = (char *) malloc(10);

strcpy(str, “Computer”);

printf(“String = %s\n”, str);

p = (type*) realloc (p, n*sizeof(type) );

if (p == NULL)

{

printf("Insufficient memory\n");

exit(0);

}

strcpy(str, “Computer Science and Engineering”);

printf(“String =%s\n”, str);

} �

An array is a collection of similar data items stored in consecutive memory locations. All elements of the array share a common name.

Each element in the array can be accessed by the subscript (or index).

Number of items in an array = upper bond – lower bond + 1

= ub – lb + 1 (ex: int arr[8]=8-0+1=9 )

The location of any element at a[j] is given by:

Loc A[j] = base address + x

Distance from base address : x = w * (j – lb )

Loc A[j] = base address(a) + w * (j – lb)

​

​

​

​

​

​

​

​

​

Different Operation on an array:

Traversing Inserting Deleting searching sorting

​

Multidimensional arrays:

A[i][j] 2-D array

Ex:

int a[4][3] = {

{11, 22, 33},

{44, 55, 66},

{77, 88, 99},

{10, 11, 12}

};

​

The location of a[i][j] is given by:

Loc A[i][j] = base address + x + y

Displacement of ith row = w * ( j – lb2) �Loc A[i][j] = base address(a) + w * (ub2 – lb2 + 1) * (i – lb1) + w * ( j – lb2)

int main()�{�int **arr, i, j, ROWS, COLS; // **a is pointer to pointer�printf("\n Enter the number of rows and columns in the array: ");�scanf("%d %d", ROWS, COLS);�arr = (int **)malloc(ROWS * sizeof(int *));

// allocate memory as per row size�if(arr == NULL)�{�printf("\n Memory could not be allocated");�exit(-1);�}�for(i=0; i<ROWS; i++)�{�arr[i] = (int *)malloc(COLS * sizeof(int));

// Allocate Memory to Each column�if(arr[i] == NULL)�{�printf("\n Memory Allocation Failed");�exit(-1);�}

Returrn 0;�} �

void main()

{

int i,j,arr[5][5];

int **p;

p=(int**) calloc(5,sizeof(int));

for(i=0;i<3;i++)

p[i]=(int*)malloc(5*sizeof(int));

for(i=0;i<5;i++)

for(j=0;j<5;j++)

scanf("%d",(p[i]+j));

for(i=0;i<5;i++)

for(j=0;j<5;j++)

printf("%d",*(p[i]+j));

}

Structures

A structure is in many ways similar to a record.

It stores related information about an entity.�Structure is basically a user-defined data type that can store related information

A structure is therefore a collection of variables under a single name. �The variables within a structure are of different data types

Ex

struct student�{�int r_no;�char name[20];�char course[20];�float fees;�};

Here structure is similar to user defined data type.

As it’s a data type we have to define a new variable to use it

​

struct student stud1;

​

�� �

struct student�{�int r_no;�char name[20];�char course[20];�float fees;�} stud1 = {01, "Rahul", "BCA", 45000};

Or

struct student stud1 = {01, "Rahul", "BCA", 45000};

Or

​

stud1.r_no = 01;�stud1.name = "Rahul";�stud1.course = "BCA";�stud1.fees = 45000; �Or

scanf("%d", &stud1.r_no);�scanf("%s", stud1.name); � scanf("%s", stud1.course);

scanf(“%f", &stud1.fees); � �

#include <stdio.h>�#include <conio.h>�int main()�{�typedef struct complex�{�int real;�int imag;�} COMPLEX;�COMPLEX c1, c2, sum_c, sub_c;

printf("\n Enter the real and imaginary parts of the irst complex number : ");�scanf("%d %d", &c1.real, &c1.imag);�printf("\n Enter the real and imaginary parts of the �second complex number : ");�scanf("%d %d", &c2.real, &c2.imag);

sum_c.real = c1.real + c2.real;�sum_c.imag = c1.imag + c2.imag; � printf("\n The sum of two complex numbers is : %d+%di",sum_c.real, sum_c.imag); � }�

THE POLYNOMIAL

#define�typedef �MAX_DEGREE 101 / * Max degree of polynomial + 1 * /�struct {�int degree;

float coef[MAX-DEGREE];�} polynomial;

THE SPARSE MATRIX

A matrix which has few non-zero entries is called as sparse matrix

A sparse matrix wastes memory space as many entries are zero

To reduce memory space wastage we must consider alternate forms of representation.

​

�

#define MAX-TERMS 101 �typedef struct {� int col;� int row;� int value;�} term;�term a[MAX-TERMS];

​

​

The matrix is represented as a triplet

( Row, Col, Value)

The first row a[0] contains

No.of Rows in original Matrix

No of Column in original Matrix

No of Non Zero Values

​

A[0][0]=6

A[0][1]=6

A[0][2]=8

Transposing a Matrix

for all elements in column j�place element <i, j, value > element in <j, i, value>

char str[] = {'H', 'E', 'L', 'L', 'O', '\0'};

char name[5][10] = {"Ram", "Mohan", "Shyam", "Hari","Gopal"};

STACKS

A stack is a linear data structure, where elements can be added and deleted from the same end called top of the stack.

​

Stack exhibits Last In First Out (LIFO) behavior

Operation of adding / Inserting elements to the stack is called as PUSH operation

Operation of removing / deleting elements to the stack is called as POP operation

Stack has a capacity defined STACK_SIZE

​

Stack full condition:- If total number of elements on the stack are equal to STACK_SIZE , push operation gives STACK FULL error ( Stack Overflow error)

​

Stack Empty: If stack is empty, calling operation POP on stack results in stack empty error ( Stack Underflow Error)

Static using array

#define stack_size 100

typedef stack

{

int Key;

} ;

stack st[stack_size];

int top = -1;

Dynamic representation

typedef stack

{

int key;

} ;

stack *st;

malloc(stack, sizeof(*stack));

Capacity=0;

Top=-1;

​

/* when stack full condition error occurs following code is executed */

realloc(stack,2*capacity*sizeof(stack));

/*this allocates additional space*/

​

int stack[MAX];

void push(int st[], int val)�{

if(top == MAX-1)

{

printf("\n STACK OVERFLOW");

}� else�{� top++;� st[top] = val;�}�}

int pop(int st[])�{�int val;�if(top == -1)�{� printf("\n STACK UNDERFLOW");� return -1; }�else�{� val = st[top];� top--;� return val; }�}

void display(int st[])�{int i;�if(top == -1)�printf("\n STACK IS EMPTY");

else�{�for(i=top; i>=0; i--)�printf("\n %d",st[i]); }

int stacktop(int st[])�{

if(top == -1)

{

printf("\n STACK IS EMPTY");�return -1; }�else�return (st[top]); }

Reversing a list�Parentheses checker Conversion of an infix expression into a postfix expression�Evaluation of a postfix expression�Conversion of an infix expression into a prefix expression�Evaluation of a prefix expression�Recursion

Multiple Stack

QUEUE

A queue is a FIFO (First-In, First-Out) data structure in which the element that is inserted first is the first one to be taken out. The elements in a queue are added at one end called the REAR and removed from the other end called the FRONT.

#define MAX 10 // Changing this value will change length of array�int queue[MAX];�int front = -1, rear = -1;

​

void insert()�{�int num;�printf(“\n Enter the number to be inserted in the queue : “);�scanf(“%d”, &num);�if(rear == MAX-1)

{

printf(“\n OVERFLOW”);

Return ;

}�else

if(front == -1 && rear == -1)�front = rear = 0;�else�rear++;�queue[rear] = num;�} �

int delete_element()�{� int val ;

if(front == -1 || front>rear)�{

printf(“\n UNDERFLOW”);�return -1;

}�else�{�val = queue[front];�front++;�if(front > rear)�front = rear = -1;�return val;�}�}

void display()

{

int i;

printf(“\n”);

if(front == -1 || front > rear)

printf(“\n QUEUE IS EMPTY”);

else

{

for(i = front;i <= rear;i++)

printf(“\t %d”, queue[i]);

}

}

TYPES OF QUEUES�A queue data structure can be classified into the following types:�1. Circular Queue

2. De-queue ( Double Ended Queue)

3. Priority Queue

4. Multiple Queue �

Double Ended Queue (DeQueue)

Input restricted

Output Restricted

Priority Queue

Multiple Queues

Linked List

• Linear link list data structure is a collection of NODES
• Each node has two or more parts. One of which points to the address of next node called LINK part.
• The other parts holds DATA, hence can be called DATA part
• The last node in the linked lists points to NULL to designate end of linked list
• A linked list can have an additional node that points to the first node in the list called head node / Start Node.

struct node {

int data;

struct node *next; } �

#define NUMNODES 500�struct nodetype {�int info, next;

}�struct nodetype node[NUMNOOES];

avail = 0;�for (i = 0 i < NUMNODES-1; i++)�node(i] .next= i + 1;�node[ NUMNODES-1].next = -1; �

int getnode(void)

{�int p;�if (avail == -1)

{�printf("overflow\n");�exit(1);

}�p = avail;�avail =node[avail].next;�return(p);�}

void freenode(int p)

{�node[ p. next] = avail;�avail = p;�return;

}

void insafter(int p, int x )

{

int q;� If(p=-1) {�printf("vod insertion\n');�return; }�q = getnode();�node[q].info=x;�node[q] next = node[p] .next;�node[p].next=q; return;�}

NOOEPTR getnodé(void)

{

NODEPTR p;

p= (NODEPTR) malloc (sizeof(struct node));

return(p);

}

void freenode(NODEPTR p)

{

free(p);

}�

struct node

{

int info;

struct node *next;

}

typedef struct node *NODEPTR; �

p= (NODEPTR) malloc(sizeof (struct node));

NODEPTR list;

list=NULL;

p->info=10;

p=list;

list=p;

/*free(p)*/

Linked list as stack implementation

struct node

{�int info;�struct node next;

};�typedef struct node *NODEPTR; �NODEPTR p ;�

P=getnode();�

NODEPTR push(int x)

{

NODEPTR p;

P=getnode();

P->info=x;

P=list;

List=p;

Return list;

}

int pop()

{

NODEPTR P=list;

If(p==NULL)

{ printf(“List empty”);

return 0;

}

X=p->info;

List=p->next;

Free(p);

Return x;

}

Void display()

{

NODEPTR p;

P=list;

If(p==NULL)

{ printf(“List empty”);

return ;

}

For(p=list;p!=NULL;p=p->next)

printf(“%d”,p->info);

return; }

void insafter(NODEPTR p, int x)

{�NODEPTR q;�if (p ==NULL)

{�printf("void insertion\n”);�exit(1);

}�q= getnode();�q -> info =x;�q -> next = p -> next;�P -> next =q;�} �

void deafter(NODEPTR p, int *px)�{

NODEPTR q;�if((p == NULL) || (p -> next == NULL))�{

printf(ojd deletion\n);�exit(1);

}�q=p -> next;�px = q -> info.;�P -> next = q -> next;�freenode(q);�} �

LINKED LIST PRIORITY QUEUES

void place(NOOEPTR *plist, int x)

{�NOOEPTR p, q;�q = NULL;�for (p =*plist; p != NULL && x > p->info; p =p->next)

q =p;

�if (q ==NULL)

push(*plist, x);�else�insafter(q, x);

}

int pop()

{

NODEPTR P=list;

If(p==NULL)

{

printf(“List empty”);

return 0;

}

X=p->info;

List=p->next;

Freenode(p);

Return x;

}

//Insert at end of list

void insend(NODEPTR *piist, int x)

{�NODEPTR p, q;�p= getnode();�p->info= x;�p->next = NULL; �if (*pljst == NULL) �*plist = p:�else�for (q = *plist; q->next != NULL; q =q->next);

q->next = p;�} ��

NODEPTR search(NODEPTR list, int x)

{�NODEPTR p;�for (p = list; p != NULL; p = p->next)�if (p->info== x)�return (p);�else�return (NULL);�} �

typedef struct poly_node *poly_pointer;�typedef struct poly_node

{�int coef;�int expon;�poly_pointer link;�};

poly_pointer a,b,d; �

NODEPTR insert(NODEPTR *clist,int x)

{

NODEPTR p;

p=getnode();

P->info=x;

If(CLIST==NULL)

{

CLIST=p;

CLIST->next=CLIST; }

Else

{ p->next=clist->next;

clist->next=p;

}

Return clist; }

Int delete(NODEPTR *clist)

{

NODEPTR p;

If(clist==NULL)

{ printf(“List empty”);

exit(0); }

p=clist->next;

X=P->info;

If( p->next==clist->next)

clist=NULL;

else

c->next=p->next;

}

int empty(NODEPTR *pstack)

{�return ((pstack == NULL) ? TRUE : FALSE);

} �

Void push(NODEPTR pstack, int x)�{�NODEEPTR p;�P – getnode();�p->info=x;�if (empty(pstack) ==TRUE)�pstack =p;�else�p->next =(*pstack) -> next;�(*psrack) -> next =p;

}�

int POP(NODEPTR pstack)�{�int x;�NOOEPTR p;�if (empty(pstack) ==TRUE)

{�printf('stack underflow\n");�exit(1);� }

P = (*pstack) -> next;�x = p->info;�if (p== *pstack)�*pstack = NULL;�else�(pstack) -> next =p->next;�freenode(p);�return(x);�}�

void insert(NODEPTR *pq, int x)�{

NODEPTR p;�p =getnode();�p->info =x;�if (empty(pq) == TRUE)�*pq =p;�else�p->next=(*pq) -> next;�(*pq) -> next =p;�*pq =p;�return;�}�// CLIST as a queue

int Delete(NODEPTR pq)�{�int x;�NOOEPTR p;�if (empty(pq) ==TRUE)

{�printf(‘Queue Empty\n");�exit(1);� }

P = (*pq) -> next;�x = p->info;�if (p== *pq)�*pq = NULL;�else�(pq) -> next =p->next;�freenode(p);�return(x);�}�

SPARCE MATRIX REPRESENTAION AS LINKED LIST

• Represent each column of a sparse matrix as a circularly linked list with a head node.
• Similar representation for each row of a sparse matrix.
• Each node has a tag field, which we use to distinguish between head nodes and entry nodes ( Head Node 3 fields and Entry Node 5 fields)
• Head node has three additional fields: down, right, Next
• down field to link into a column list and the right field to link into a row list and The next field links the head nodes together
• head node for row i is also the head node for column i
• total number of head nodes is equal to max number of rows and columns
• Each entry node has five fields in addition to the tag field: row, col, down, right, value
• down field to link to the next nonzero term in the same column and the right field to link to the next nonzero term in the same row ���������

Representation of sparse Matrix as

Circular Linked List

Doubly linked list

Doubly Linked list contains two pointes , 1 pointing to previous node, called left pointer

Right pointer points to Successor node or next node

Hence each node has Left pointer and right pointer

They are symmetric in nature

The list can be traversed in any direction

A Doubly Linked List ( DLL) may contain a header node

Left(right(p))=p=right(left(p))

ALGORITHM BruteForceStringMatch(T [0..n - 1], P[0..m - 1])�//Implements brute-force string matching�//Input: An array T [0..n - 1] of n characters representing a text and�for i ← 0 to n - m do�j ← 0�      while j < m and P[j] = T[i + j] do�                    j ← j + 1�                  if j = m 

return i�return -1

Knuth-Morris-Pratt Algorithm�

KMP algorithm is used to find a "Pattern" in a "Text".

This algorithm compares character by character from left to right.

Whenever a mismatch occurs, it uses a preprocessed table called "Prefix Table" to skip characters comparison while matching.

The prefix table is also known as "Longest proper Prefix which is also Suffix" LPS Table.

Steps for Creating LPS Table (Prefix Table)

• Step 1 - Define a one dimensional array with the size equal to the length of the Pattern. (LPS[size])
• Step 2 - Define variables i & j. Set i = 0, j = 1 and LPS[0] = 0.
• Step 3 - Compare the characters at Pattern[i] and Pattern[j].
• Step 4 - If both are matched then set LPS[j] = i+1 and increment both i & j values by one. Goto to Step 3.
• Step 5 - If both are not matched then check the value of variable 'i'. If it is '0' then set LPS[j] = 0 and increment 'j' value by one, if it is not '0' then set i = LPS[i-1]. Goto Step 3.
• Step 6- Repeat above steps until all the values of LPS[] are filled.

a pattern...

​

void computeLPSArray(const 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++;

}

}

}

}

KMPSearch

(const char* pat, const char* txt, int* count)

{

computeLPSArray(pat, M, lps);

while ((N - i) >= (M - j)) {

if (pat[j] == txt[i]) {

j++; i++;

}

if (j == M) {

result[*count] = i - j + 1; (*count)++;

j = lps[j - 1];

}

else if (i < N && pat[j] != txt[i]) {

if (j != 0) {

j = lps[j - 1];

}

else {

i = i + 1;

}

}

}

free(lps);

return result;

}