Last active
November 11, 2019 19:43
-
-
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.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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)); | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
please tell me about this programme error