find all common part between vector-CodePudding

I have n vectors with unique integers. I want to find all the common part between them. Is there any specific algorithm or data struct for this problem?

example:

std::vector<int> a = {0,1,2,3,4,5,6,7,8,9,10,11,12,13};
std::vector<int> b = {1,7,8,9,2,10,11,12};
std::vector<int> c = {4,9,8,7,0,1,2,3};

result: ignore result with only one interge

7,8,9 between a and b

10,11,12 bewteen a and b

0,1,2,3 between a and c

CodePudding user response：

it seems to me that you are looking for Longest Common Subsequence

CodePudding user response：

if you want all common subarrays with a length greater than 1, then for each element from the first array iterate over all elements in the second array if you match two elements then go to the next element in the first and second array, and so on.

for (int i = 0; i < n; i  ) {
    for (int j = 0; j < m; j  ) {
        if (arr1[i] == arr2[j]) {
            int ii = i, jj = j, cnt = 0;
            std::vector<int> res;
            res.push_back(arr1[ii]);
            while (  ii < n and   jj < m and arr1[ii] == arr2[jj])res.push_back(arr1[ii]);
            if (res.size() > 1) {
                for (auto x: res)std::cout << x << " ";
            }
        }
    }
}

time complexity:O(n^3)

and this another way by LCS.

memset(dp, 0, sizeof dp);
    for (int i = 1; i <= n; i  ) {
        for (int j = 1; j <= m; j  ) {
            dp[i][j] = 0;
            if (arr1[i] == arr2[j]) {
                dp[i][j] = dp[i - 1][j - 1]   1;
            }
            std::cout << dp[i][j] << " ";
        }
        std::cout << "\n";
    }
    for (int i = 1; i <= n; i  ) {
        for (int j = 1; j <= m; j  ) {
            if (dp[i][j] > 1) {
                for (int ii = i, jj = j, k = dp[i][j]; k; ii--, jj--, k--) {
                    std::cout << arr1[ii] << " ";
                }
                std::cout << "\n";
            }
        }
    }

O(n^3)