String similarity


#1

write the program to solve the below question:

For two strings A and B, we define the similarity of the strings to be the length of the longest prefix common to both strings. For example, the similarity of strings “abc” and “abd” is 2, while the similarity of strings “aaa” and “aaab” is 3.Calculate the sum of similarities of a string S with each of it’s suffixes.


#2

the output would be 11 and 3
input value for 2 string
ababaa
aa
in this string in the first case the suffix of the string are “ababaa”, “babaa”, “abaa” , “baa”. “aa” and “a”.
the similarities of these string with the string “ababaa” are 6,0,3,0,1 & 1 respectively
therefore answer would be 6+0+3+0+1+1=11
and for the second case the answer would be 2+1=3
import java.util.Scanner;
public class StringSimilarity
{
public static void main (String [] args)
{
Scanner scanner;
StringSimilarity ss = new StringSimilarity();
Scanner = new Scanner(System.in);
int no_cases= Scanner.nextInt();
for(int i=0; i<=no_cases;i–)
{
String to_proc=Scanner.next();
ss.solve(to_proc);
}
}
private void solve(String to_proc)
{
String str = to_proc;
int len=to_proc.length();
int count=0;
int total=0;
for(int i=0;i<len;i++)
{
count=o;
for(int j=i;j<len;j++)
{
if(str.charAt(j-i)==str.charAt(j))
{
count++;
}else
{
break;
}
}
total=total+count;
}
System.out.println(total+len);
}
}


#3

public class StringSimilarity {
public static int calculate(String s){
char[]arr=s.toCharArray();
int length=arr.length;
int count=length;
for(int i=1;i<length;i++){
int len=length-i;
int j=0;
for(;j<len;j++)
if(arr[j]!=arr[j+i]){
break;
}
count+=j;
}
return count;
}
/*
public static int calculate(String s){
int count=s.length();
for(int i=1;i<s.length();i++){
count+=similarCount(s,s.substring(i));
}
return count;
}
private static int similarCount(String s, String sub){
for(int i=0;i<sub.length();i++)
if(s.charAt(i)!=sub.charAt(i))
return i;
return sub.length();
}*/
public static void main(String[] args) {
Scanner scanner = new Scanner( System.in );
int n=scanner.nextInt();
for(int i=0;i<n;i++){
String s=scanner.next();
System.out.println(calculate(s));
}
}