가장 긴 공통 하위 시퀀스 찾기 : 내 메서드

Question

2 개의 문자열 중에서 가장 긴 공통 하위 시퀀스를 구현하려고합니다. 내 방법은 여기에 게시 된 것과 조금 다릅니다. 나는 해결책에 가깝지만 거의 문제가 없다. 도와주세요.

내 문제 : 원하는 출력 : 메탈리카 전류 출력 : etallica

내 코드는 다음과 같습니다

import java.util.ArrayList; 
import java.util.Stack; 

public class CommonSubS { 

public static void main(String[] args) { 

    ArrayList<Character> ss = new ArrayList<>(); 
    String s1 = "metallicarules"; 
    String s2 = "rulmetallicales"; 
    ArrayList<ArrayList<Character>> one = new ArrayList<>(); 
    char[] first = s1.toCharArray(); 
    char[] second = s2.toCharArray(); 
    int j = 0; 
    int current = 0; 
    int mainIndex = 0; 
    ArrayList<Character> sec = new ArrayList<>(); 

    // search for each char in second    
    for(int i = 0; i<second.length; i++) 
    {  
     j = current; 
     // search for each char in first 
     while(j<first.length) 
     { 
      // if match found, add to the arraylist 
      if(first[j] == second[i]){ 

       sec.add(first[j]); 
       current = j+1; 
       break; 
      } 
      else 
      { // if different char occured in between, 
       // save current arraylist in one 
       // and go forward 
       one.add(sec); 
       sec = new ArrayList<>(); 
       j++; 
       current = 0;   
      } 

     } 
    } 

    for(ArrayList<Character> s: one) 
    { 
     for(Character c: s) 
     { 
      System.out.print(c); 
     } 
     System.out.println();  
    } 

    } 
} 

/* 
desired output: metallica 
current output: etallica 
*/ 

내가 거기에 다른 방법이 있지만 간단한 방법을 사용하여 구현하려고 알고있다. 문제를 지적하십시오.

Answer 1

나는 문제가 있으므로 다음 반복이가있는 다음 문자에서 시작하여 내가 증가 가져옵니다이며, 첫 번째 단어의 마지막 전자와 두 번째 단어의 메탈리카에서 m을 비교 생각 e (두 번째 단어), 그 이유는 처음에 m을 얻지 못하는 이유입니다. 어쩌면 공통 서브 시퀀스를 종료 할 때마다 i = i-1을 사용하면됩니다.

Answer 2

알고리즘이 어떻게 작동하는지 아직 정확하게 알지 못하지만, j의 값이 너무 빨리 커지고 있다고 생각합니다. else 블록을 변경하여 매번 j을 0으로 재설정하면 코드에서 "metallica"의 출력을 생성합니다.

  else 
      { // if different char occured in between, 
       // save current arraylist in one 
       // and go forward 
       one.add(sec); 
       sec = new ArrayList<>(); 
       j = 0; // Start checking from the beginning of the string 
       current = 0; 
       break; // This will exit the while loop and move on to the next value of i 
      }