세 시퀀스의 가장 긴 공통 서브 시퀀스

Question

C++을 사용하여 세 시퀀스의 int 중 가장 긴 공통 서브 시퀀스를 해결하려고합니다. 문제는 클래식입니다.

작업입니다. B = (b1, b2, ..., bm) 및 C = (c1, c2, ..., cl)의 3 개의 시퀀스 A = (a1, a2, ..., an) 그들의 긴 공통 시퀀스, 즉, 지수 1 ≤ I1 < I2 < 존재 되도록 최대의 음이 아닌 정수 P ··· <의 IP ≤ n을 1 ≤ J1 < J2 < ··· < JP주의 ≤ m을, 1 ≤k1 < k2 < ······ < kp ≤ l 그러한 ai1 = bj1 = ck1,. . . , aip = bjp = ckp

입력 형식. 첫 번째 줄 : n. 두 번째 줄 : a1, a2,. . . ,. 세 번째 줄 : m. 네 번째 라인 : b1, b2,. . . , bm. 다섯 번째 줄 : l. 여섯 번째 줄 : c1, c2,. . . , cl.

제약. 1≤n, m≤1≤100; -109 < ai, bi, ci < 109.

출력 형식. 출력 p. 내 코드

내 솔루션은 내가 오류 여기

을 찾을 수 있지만, 28 29 이상의 경우를 확인했다입니다 :

귀하의 코드가 정말 같은 문제에 대한 복잡 보인다

#include <iostream> 
#include <vector> 
#include<algorithm> 
using namespace std; 
using std::vector; 

int get_position(int alpha,vector<pair<int,int>> vect, int A,int B) { 
    if (alpha == 8) { 
     int gamma = 0; 
    } 
    if (A != B) { 
     if (vect[A].first == alpha) { 
      return vect[A].second; 
     } 
     if (vect[B].first == alpha) { 
      int petitb = B; 
      while ((petitb > A) && (vect[petitb].first == alpha)) 
       petitb--; 
      if (vect[petitb].first == alpha) return vect[petitb].second; 
      else { 
       petitb++; 
       if (vect[petitb].first == alpha) return vect[petitb].second; 
      } 

      return vect[B].second; 
     } 
     int mid = (A + B)/2; 
     if (vect[mid].first == alpha) { 
      return vect[mid].second; 
     } 
     if (vect[mid].first > alpha) { 
      if (mid == B) return -1; 
      return get_position(alpha, vect, A, mid); 
     } 
     else { 
      if (mid == A) return -1; 
      return get_position(alpha, vect, mid, B); 
     } 

    } 
    else { 
     if (vect[A].first == alpha) { 
      return vect[A].second; 
     } 

    } 
    return -1; 
} 
int get_relative_pos(int alpha, vector<pair<int, int>> vect,vector<int> V, int A, int B) { 

    int absolute = get_position(alpha, vect, 0, vect.size()-1); 
    if ((absolute >= A) && (absolute <= B)) { 
     return absolute; 
    } 
    if (absolute > B) 
    return -1; 
    if (absolute < A) { 
     if (V[A] == alpha) { return A; } 
     else { return -1; } 
    } 
    return -1; 
} 
bool comp1(pair<int, int>A, pair<int, int>B) { 
    if (A.first == B.first) 
     return A.second < B.second; 
    return A.first < B.first; 
} 
int explore(vector<int> &a, vector<int> &b, vector<int> &c, int PA, int PB, int PC) { 
    int length = 0; 
    while ((PA<a.size()) && (PB<b.size()) && (PC<c.size())) { 
     if ((a[PA] == b[PB]) && (a[PA] == c[PC])) { 
      length++; 
      PA++; 
      PB++; 
      PC++; 
     } 
     else { 
      return length; 


     } 

    } 
    return length; 
} 
int explore2(vector<int> &a, vector<int> &b, vector<int> &c, int PA, int PB, int PC, vector<pair<int, int>> SA, vector<pair<int, int>> SB, vector<pair<int, int>> SC) { 
    int length = 0; 
    while ((PA < a.size()) && (PB < b.size()) && (PC < c.size())) { 
     if ((a[PA] == b[PB]) && (a[PA] == c[PC])) { 
      length++; 
      PA++; 
      PB++; 
      PC++; 
     } 
     else { 
      //return length; 
      int Bprim = get_relative_pos(a[PA], SB,b, PB, SB.size() - 1);//get_position(a[PA], SB, PB, SB.size() - 1); 
      int Cprim = get_relative_pos(a[PA], SC,c, PC, SC.size() - 1);//get_position(a[PA], SC, PC, SC.size() - 1); 
      if ((Bprim != (-1)) && (Cprim != (-1))) { 
       PB = Bprim; 
       PC = Cprim; 
      } 
      else { PA++; } 
     } 

    } 
    return length; 
} 
int cleanData(vector<int> &a, vector<int> &b, vector<int> &c, vector<pair<int, int>> SA, vector<pair<int, int>> SB, vector<pair<int, int>> SC) 
{ 
    int indexA, indexB, indexC; 
    for (int i = 0; i < a.size(); i++) { 
     indexB = get_position(a[i],SB,0,SB.size()-1); 
     indexC = get_position(a[i], SC, 0, SC.size() - 1); 
     if ((indexB == (-1)) || (indexC == (-1))) 
      a.erase(a.begin()+i); 
    } 
    for (int i = 0; i < b.size(); i++) { 
     indexA = get_position(b[i], SA, 0, SA.size() - 1); 
     indexC = get_position(b[i], SC, 0, SC.size() - 1); 
     if ((indexA == (-1)) || (indexC == (-1))) 
      b.erase(b.begin() + i); 
    } 
    for (int i = 0; i < c.size(); i++) { 
     indexB = get_position(c[i], SB, 0, SB.size() - 1); 
     indexC = get_position(c[i], SC, 0, SC.size() - 1); 
     if ((indexB == (-1)) || (indexC == (-1))) 
      c.erase(c.begin() + i); 
    } 
    return 0; 
} 
int lcs3(vector<int> &a, vector<int> &b, vector<int> &c) { 
    vector<pair<int, int>> SA; 
    vector<pair<int, int>> SB; 
    vector<pair<int, int>> SC; 
    for (int i = 0; i < a.size(); i++) SA.push_back(make_pair(a[i],i)); 
    for (int i = 0; i < b.size(); i++) SB.push_back(make_pair(b[i], i)); 
    for (int i = 0; i < c.size(); i++) SC.push_back(make_pair(c[i], i)); 
    sort(SA.begin(),SA.end()); 
    sort(SB.begin(), SB.end()); 
    sort(SC.begin(), SC.end()); 
    /*cleanData(a,b,c,SA,SB,SC); 
    SC.clear(); 
    SA.clear(); 
    SB.clear(); 
    for (int i = 0; i < a.size(); i++) SA.push_back(make_pair(a[i], i)); 
    for (int i = 0; i < b.size(); i++) SB.push_back(make_pair(b[i], i)); 
    for (int i = 0; i < c.size(); i++) SC.push_back(make_pair(c[i], i)); 
    sort(SA.begin(), SA.end()); 
    sort(SB.begin(), SB.end()); 
    sort(SC.begin(), SC.end());*/ 
    //write your code here 
    int ptrA, ptrB, ptrC; 
    int currentMax = 0; 
    int lcs = 0; 
    ptrA = 0; 
    ptrB = 0; 
    ptrC = 0; 
    int val = 0; 
    for (int i = 0; i < a.size(); i++) { 
     val = a[i]; 
     ptrB = get_position(val,SB,0,SB.size()-1); 
     ptrC = get_position(val, SC, 0, SC.size() - 1); 
     if ((ptrB != (-1)) && (ptrC!=(-1))) { 
      //currentMax = explore(a, b, c, i, ptrB, ptrC); 
      currentMax = explore2(a, b, c, i, ptrB, ptrC, SA, SB, SC); 
      lcs = max(lcs, currentMax); 
     } 
     if ((a.size() - i) < lcs)return lcs; 
    } 
    return lcs; 
} 

int main() { 
    size_t an; 
    std::cin >> an; 
    vector<int> a(an); 
    for (size_t i = 0; i < an; i++) { 
     std::cin >> a[i]; 
    } 
    size_t bn; 
    std::cin >> bn; 
    vector<int> b(bn); 
    for (size_t i = 0; i < bn; i++) { 
     std::cin >> b[i]; 
    } 
    size_t cn; 
    std::cin >> cn; 
    vector<int> c(cn); 
    for (size_t i = 0; i < cn; i++) { 
     std::cin >> c[i]; 
    } 
    std::cout << lcs3(a, b, c) << std::endl; 
    return 0; 
} 

Answer 1

, I 그 문제를 짐작하는 것은 단지 구현이 아니라 이것을 해결하기위한 전체 아이디어입니다.

3 개의 시퀀스 문제의 LCS는 2 개의 시퀀스의 LCS와 유사합니다. 두 경우 모두 동적 프로그래밍 접근 방식을 사용합니다. 두 시퀀스가 ​​우리가 가진 :

for i in 1 .. A.size() 
    for j in 1 .. B.size() 
     if A[i] = B[j] 
      lcs_len[i, j] = lcs_len[i - 1, j - 1] + 1 
     else 
      lcs_len[i, j] = max(lcs_len[i, j - 1], lcs_len[i - 1, j]) 

나중에, 당신은 (단지 길이) LCS를 얻으려면, 당신은 단순히 위치 (A.size(), B.size())에서 시작하고, 이전 값 향해을 역 추적해야합니다. 자세한 내용은 here을 참조하십시오.

이제 3 개의 시퀀스 문제가 생기면 하나의 루프 및 if 문을 추가해야합니다. 그러면이 문제를 해결할 수 있습니다. 그렇지 않은 경우 spoiler입니다.