-1
我正在使用C++解決三個int序列的最長公共子序列。問題是一個經典：三個序列的最長公共子序列int
任務。給定三個序列A =（a1，a2，...，an），B =（b1，b2，...，bm）和C =（c1，c2，...，cl）其 最長公共子序列，即，最大的非負整數p 使得存在索引1≤I1 < I2 <···< IP≤N，1個≤J1 < J2 <···< JP≤米， 1≤k1 < k2 <····<kp≤l使得ai1 = bj1, = ck1，...。 。 。 ，aip = bjp = ckp
輸入格式。第一行：第一行第二行：a1，a2，...。 。 。 ，一個。第三行：m。第四行：b1，b2，...。 。 。 ，bm。第五行：l。第六行 行：c1，c2，...。 。 。 ，cl。
限制條件。 1≤n，m，l≤100; -109 < ai，bi，ci < 109。
輸出格式。輸出p。
我的解決方案是爲28比29案件OK，但我找不到錯誤
這裏是我的代碼：
#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;
}
[多個序列的最長公共子序列]的可能重複（http://stackoverflow.com/questions/5752208/longest-common-subsequence-for-multiple-sequences） – cbuchart