Skip to content

Instantly share code, notes, and snippets.

@rfaisal
Last active November 11, 2019 19:43
Show Gist options
  • Select an option

  • Save rfaisal/6127944 to your computer and use it in GitHub Desktop.

Select an option

Save rfaisal/6127944 to your computer and use it in GitHub Desktop.
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.
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));
}
}
}
@nagamanichowdary
Copy link

please tell me about this programme error

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment