The Z-Algorithm solves the longest common prefix of string in a linear time. It can be used as substitutes of Suffix trees and suffix array for certain problems.

package strings; import java.util.Scanner; public class StringSimilarity { public static void solution1(){ Scanner sc = new Scanner(System.in); int num = sc.nextInt(); String input = null; char[] in = null; int len = 0; int pos=0; int overlap=0; for(int i=0; i<num; i++){ overlap=0; input = sc.next(); len = input.length(); in = input.toCharArray(); int[] z = new int[len]; /** This array will have LCP values **/ /** The Z-Algorithm: * Linear LCP calculation based on previous calculated lcp's **/ int L=0, R=0; int sum=0; for(int j=1; j<len; j++){ if(j>R){ L=R=j; while(R<len && in[R-L]==in[R]) R++; z[j]=R-L; R--; } else{ int k=j-L; if(z[k]<R-j+1) z[j]=z[k]; else{ L=j; while(R<len && in[R-L]==in[R]) R++; z[j]=R-L; R--; } } sum=sum+z[j]; } /*for(int ii:z) System.out.println(ii); */ System.out.println(sum+len); } } public static void main(String[] args){ StringSimilarity.solution1(); } }

Yash Sharma is a Big Data & Machine Learning Engineer, A newbie OpenSource contributor, Plays guitar and enjoys teaching as part time hobby.

Talk to Yash about Distributed Systems and Data platform designs.