# KMP Agorithm (Part 1 : Constructing LPS Array)

Tue Feb 08 2022 12:02:37 GMT+0000 (UTC)

```// Efficient Code O(n)

import java.util.*;
import java.io.*;

class GFG {

static void fillLPS(String str, int lps[])
{
int n=str.length(),len=0;
lps[0]=0;
int i=1;
while(i<n){
if(str.charAt(i)==str.charAt(len))
{len++;lps[i]=len;i++;}
else
{if(len==0){lps[i]=0;i++;}
else{len=lps[len-1];}
}
}
}

public static void main(String args[])
{   String txt = "abacabad";int[] lps=new int[txt.length()];
fillLPS(txt,lps);
for(int i=0;i<txt.length();i++){
System.out.print(lps[i]+" ");
}
}
}

// Naive Code O(n^3)

import java.util.*;
import java.io.*;

class GFG {

static int longPropPreSuff(String str, int n)
{
for(int len=n-1;len>0;len--){
boolean flag=true;
for(int i=0;i<len;i++)
if(str.charAt(i)!=str.charAt(n-len+i))
flag=false;

if(flag==true)
return len;
}
return 0;
}

static void fillLPS(String str, int lps[]){
for(int i=0;i<str.length();i++){
lps[i]=longPropPreSuff(str,i+1);
}
}

public static void main(String args[])
{   String txt = "abacabad";int[] lps=new int[txt.length()];
fillLPS(txt,lps);
for(int i=0;i<txt.length();i++){
System.out.print(lps[i]+" ");
}
}
} ```
content_copyCOPY

Two methods of LPS (Longest Proper Prefx Suffix) Array are discussed. One method has time complexity O(n^3) and other method is O(n).