вычислить перекрытие между двумя строками в Java

Question

Я хочу написать функцию, которая принимает две строки в качестве входных данных и возвращает перекрытие между ними. Например: S1 = «ABCD» и S2 = «CDBA», функция должна возвращать перекрытие = 2, потому что суффикс первой строки и префикса второго аналогичен 2 char «CD» i, напишите этот код:

public class JavaStringArrayTests { 
    public static void main(String[] args){ 
     JavaStringArrayTests jj= new JavaStringArrayTests(); 
     System.out.print(jj.overlap()); 
    } 

    int overlap() { 
     String f1 = "ABCD"; 
     String f2 = "DBCA"; 
     int max=0; 
     char[] first= f1.toLowerCase().toCharArray(); 
     char[] second= f2.toLowerCase().toCharArray(); 

     for (int i=0; i<4; i++) { 
      for (int i2=i; i2<4; i2++) { 
       for (int j=0; j<4; j++) { 
        if (first[i]==second[j]) 
         max++; 
        else break; 
       } 
       if (max==0) 
        break; 
      } 
     } 
     return max; 
    } 
} 

этот код работает со строками без повторения, но когда я ставлю Например: S1 = «ATTC» и S2 = «TTCA», он не работает, есть ли какие-либо идеи для расчета этого? Спасибо

Answer 1

Вам просто нужно два скользящих окна в строки данных. Регулируя ширину окна, вы определяете перекрытие.

/** 
* @author aupanner 
*/ 
public class Overlap { 

    static int calculateOverlap(final String s1, final String s2) { 
     final int s1len = s1.length(); 
     final int s2len = s2.length(); 
     final int maxlen = Integer.min(s1len, s2len); 

     // from the longest overlap to the shortest possible. 
     for (int len = maxlen; len > 0; len--) { 
      // sliding window into s1 from 0 
      for (int toffset = 0; toffset + len <= s1len; toffset++) { 
       // sliding window into s2 from 0 
       for (int ooffset = 0; ooffset + len <= s2len; ooffset++) { 
        //System.out.println("Comparing s1.regionMatches(" + toffset + ", s2, " + ooffset + ", " + len + ")"); 
        if (s1.regionMatches(toffset, s2, ooffset, len)) { 
         return len; 
        } 
       } 
      } 
     } 

     // no overlap found. 
     return 0; 
    } 

    /** 
    * @param args the command line arguments 
    */ 
    public static void main(String[] args) { 
     String s1 = "ABCD"; 
     String s2 = "DBCA"; 
     System.out.println("Maximum overlap is: " + calculateOverlap(s1, s2)); 
     String f1 = "ATTC"; 
     String f2 = "TTCA"; 
     System.out.println("Maximum overlap is: " + calculateOverlap(f1, f2)); 
    } 
} 

Answer 2

Вместо использования 3 для цикла используйте только 2 и назначьте и проверьте значение j на основе max и i соответственно.

Примечание: Производить результат как «0», если обе строки равны

for(int i=0; i<4; i++){ 
    for(int j=max; j<i; j++){ 
     if (first[i]==second[j]){ 
      max++; 
      break; 
     } 
     else 
      break; 
    } 
}