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

Run Length Encoding | Programming In Java

  Given a string, Your task is to complete the function   encode   that returns the   run-length encoded  string for the given string. eg  if the input string is “wwwwaaadexxxxxx”, then the function should return “w4a3d1e1x6″. You are required to complete the function  encode  that takes only one argument the string which is to be encoded and returns the encoded string. Example 1: Input: str = aaaabbbccc Output: a4b3c3 Explanation: a repeated 4 times consecutively b 3 times, c also 3 times. Example 2: Input: str = abbbcdddd Output: a1b3c1d4 Your Task: Complete the function  encode()  which takes a character array as an input parameter and returns the encoded string. Expected Time Complexity:  O(N), N = length of a given string. Expected Auxiliary Space:  O(1) Constraints: 1<=length of str<=100 Solution: import java.util.*;   class RLEncoding {    public static void main(String[] args)     {         Scanner sc = new Scanner(System.in);        int T = sc.nextInt();   sc.nextLi
Post a Comment
Read more

if....else-Basic Programming Concepts With psudo Code

if...else if...else is a statement. it based on some condition. if the condition can be true the block of if statements can execute other wise the block of else statements can executed. syntax if([condition]) { //statements or code; } else { //statement or code; } example, #include<stdio.h> #include<conio.h> main() int num=1; { if(num==1) { printf("\n its true"); } else { printf("\n its false"); } }
Post a Comment
Read more