Skip to main content

LPS(Longest Prefix Which Is Also Suffix) Array Generation Using Java

import java.util.*;




//Longest Prefix Which Is Also Suffix Which Is Used To Found a Pattern Through
Avoid Repeated Characters in Given String. We Will Discuss KMP ALGORITHM TO
Find A Pattern In Given String Latter.
class lbs{

public static void main(String[] args){

Scanner in=new Scanner(System.in);

//Get Input From User
String s=in.nextLine();

//Convert String Into Char Array
char[] ch=s.toCharArray();

int n=s.length();

int[] lbsArr=new int[n];

int j=0,i=1;

lbsArr[0]=0;

//LPS ARRAY ALGORITHM

/*
i=1;
j=0;
string s="aaab"

while i<n
if s[i]==s[j]:
lpsArr[i]=j;
j=j+1
i=i+1
else:
if j==0:
lbsArr[j]=0
i=i+1
else:
j=lbsArr[j-1];
lbsArr[i]=j

*/

while(i<n){
if(ch[j]==ch[i]){
lbsArr[i]=++j;
i+=1;
}
else{
if(j==0){
lbsArr[i]=j;
i+=1;
}
else{
j=lbsArr[j-1];
lbsArr[i]=j;
}
}
}

for(int k=0;k<n;k++){
System.out.print(lbsArr[k]);
}
}

}

output 1:
aaaa
0123

output 2:
abcd
0000

output 3:
aabaacaabaa
01012012345
Labels:

Comments

Post a Comment

Popular posts from this blog

Class is a collection of similar objects. Which have common properties

Class is a collection of similar objects. Which have common properties. Syntax class class_name {        //member functions and variables. } How to create a objects for class class_name c=new class_name; We can access the member variable and member methods using dot operator. c.member_function(); Eg : class bike { void fun() { System.out.println("member method"); } public static void main(String[] args) { bike B=new bike(); B.fun(); } } output member method
Post a Comment
Read more

Height Of Tree-Using Java Programming

  class node{ int data; node left; node right; node( int data){ this .data=data; } } class treeHeight{ node root; treeHeight(){ root= null ; } public static void main( String [] args){ treeHeight t=new treeHeight(); t.insert( 15 ); t.insert( 20 ); t.insert( 10 ); t.insert( 5 ); t.insert( 2 ); System.out.println(t.height(t.root)); } public void insert( int data){ root=addNode(root,data); } public node addNode(node root, int data){ if (root== null ){ return new node(data); } else if (root.data<data){ root.right=addNode(root.right,data); } else if (root.data>data){ root.left=addNode(root.left,data); } else { return root; } return root; } /* 15,20,10,5 Regression Is Used To Divide a Hu...
Post a Comment
Read more