최장 공통 부분 배열을 찾는 방법을

Question

여기 내 문제는 다음과 같습니다

내가 가진

array1 = [0, 1, 2, 3, 4]; 
array2 = [9, 1, 2, 3, 4]; 
array3 = [10, 1, 2, 11, 4]; 
array4 = [12, 1, 2, 13, 4]; 
array5 = [14, 1, 2, 15, 4]; 

가장 긴 공통 부분 배열을 발견하는 : 나는 자바 스크립트에서 이와 같은 정수의 5 개 배열을 가지고있다. 이 경우 배열을 검색해야합니다 : [1, 2, 4].

레코드의 경우 배열 내에서 반복을 찾지 않을 것이고 내 목표는 실행 속도가 아닙니다.

Answer 1

이 시도

감사 :

var array1 = [0, 1, 2, 3, 4]; 
var array2 = [9, 1, 2, 3, 4]; 
var array3 = [10, 1, 2, 11, 4]; 
var array4 = [12, 1, 2, 13, 4]; 
var array5 = [14, 1, 2, 15, 4]; 

// join everything into one array 
var all = array1.join(',')+','+array2.join(',')+','+array3.join(',')+','+array4.join(',')+','+array5.join(','); 
all = all.split(','); 

// get an object with all unique numbers as keys 
var keys = {}; 
for(var i=0; i<all.length; i++) keys[all[i]] = 1; 
console.log(keys); 

// generate an array with values present in all arrays 
var common = []; 
for(var x in keys) { 
    if(array1.indexOf(parseInt(x)) != -1 && array2.indexOf(parseInt(x)) != -1 && array3.indexOf(parseInt(x)) != -1 && array4.indexOf(parseInt(x)) != -1 && array5.indexOf(parseInt(x)) != -1) { 
    common.push(x); 
    } 
} 
console.log(common); 

Answer 2

나는 이것이 당신에게 좋은 시작을 줄 수있는 것 같아요 : 내 스크립트가 각 요소의 개수가 포함 된 객체를 반환합니다. 그러나 지금은 첫 번째 배열을 기본으로 사용합니다.

var array1 = [0, 1, 2, 3, 4]; 
var array2 = [9, 1, 2, 3, 4]; 
var array3 = [10, 1, 2, 11, 4]; 
var array4 = [12, 1, 2, 13, 4]; 
var array5 = [14, 1, 2, 15, 4]; 
var array6 = [13, 1, 2, 18, 4]; 

var mainArr = [array1, array2, array3, array4, array5, array6] 

function getCommonElement(arr){ 
    var subLength = arr[0].length; 
    var resultArr = new Array(); 
    var ret = new Object(); 
    for(var k=0;k<subLength;k++){ 
     var temp = new Array(); 
     for(var i=0;i<arr.length;i++){ 
      temp.push(arr[i][k]); 
     } 
     resultArr.push(temp); 
    } 
    for(var i=0;i<arr[0].length;i++){ 
     ret[arr[0][i]+''] = resultArr[i].join('').split(arr[0][i]+'').length - 1; 
    } 
    return ret; 
} 

건배.

Answer 3

#define MAX(a,b) a>b?a:b 

int main(int argc, char* argv[]) 
{ 
     if(argc < 2) 
       return -1; 

     int x = strlen(argv[1])+1; 
     int y = strlen(argv[2])+1; 

     int i,j,k,l; 

     int longest =0; 
     char* LCS = (char*)malloc(sizeof(char)*MAX(x,y)); 

     int** arr = (int**)malloc(sizeof(int*)*x); 

     for(i=0;i<=y;i++) 
     arr[i] =(int*) malloc(sizeof(int)*y); 

     for(i=0;i<=x;i++) 
      for(j=0;j<=y;j++) 
      { 
       arr[i][j] = 0; 
      } 

     for(i=0;i<x;i++) 
       for(j=0;j<y;j++) 
       { 
         if(argv[1][i] == argv[2][j]) 
           arr[i+1][j+1] = arr[i][j]+1; 
         if(arr[i+1][j+1] > longest) 
         { 
           longest =arr[i+1][j+1]; 
           memset(LCS,0,MAX(x,y)); 
           for(k=0,l=i;k<=longest;k++,l--) 
             LCS[k] = argv[1][l]; 

         } 
       } 

     printf(" %s",argv[2]); 
     for(i=0;i<x;i++) 
     { 
       printf("\n%c",argv[1][i]);    
       for(j=0;j<y;j++) 
       { 
       printf("%d",arr[i][j]);                     
       } 
     } 

     printf("\nLongest Common Subarray : %s\n",LCS); 
     return 0; 
}