Pattern Matching

Program : Pattern Matching

import java.io.*; //To implement I/O operations

class link
{
char data;
link next; //next link in list
link (char d) //constructor
{
data=d; //initialize data
}
}

class linklist
{
link first; //ref to first link on list
linklist() //constructor
{
first=null; //no links on list yet
}
void insert(char d) //To insert into the list
{
link node=new link(d); //make new link
node.next=first;
first=node;
} //End of function create
void find(linklist m,linklist pat) //To check for matching pattern
{
link c,mstr,substr;
c=m.first;
while (c!=null)
{
mstr=c;
substr=pat.first;
while ((mstr!=null)&&(substr!=null))
{
if ((mstr.data==substr.data))
{
mstr=mstr.next;
substr=substr.next;
}
else break;
}
if(substr!=null)
c=c.next;
else
{
System.out.println("GIVEN PATTERN EXIST IN THE MAIN STRING");
break;
}
}
if(c==null)
System.out.println("GIVEN PATTERN NOT EXIST IN THE MAIN STRING");
} //end of function find
} //end of class linklist

public class Patmatch //The main class circularqueue
{
public static void main(String args[]) //main function
{
try //the try block
{
BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
String st;
int i=0;
char a;
linklist mainlist=new linklist(); //make new main string
linklist pattern=new linklist(); //make new sub string
linklist o=new linklist(); //for find function
System.out.println("ENTER THE MAIN STRING");
st=in.readLine();
int cnt=st.length();
for(i=0;i<cnt;i++)
{
mainlist.insert(st.charAt(i)); //Assign values to string
}
System.out.println("enter the substring:");
st=in.readLine();
int cn=st.length();
for(i=0;i<cn;i++)
{
pattern.insert(st.charAt(i)); //Assign values to string
}
o.find(mainlist,pattern);
}
catch (Exception e) //To catch I/O Exception
{
}
} //End of main function
} //End of main class patmatch