// 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]+" "); } } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter