Z-Algorithm for Longest Common Prefix of string

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();
}
}```