Sum of LCP's of String with all its suffixes - The Z-Algorithm (linear time)

StringSimilarity.java

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