算法标签

$后缀自动机、字符串匹配、排序算法、去重算法$

解题思路

题意分析

本题的核心是在两个代码库（TDP 代码库和 JCN 代码库）之间找出可能的侵权代码段。具体来说，需要从 JCN 代码库中找出与 TDP 代码库中最长的连续匹配子串，并且这些子串不能相互重叠。同时，对于每个测试用例，需要根据输入的参数 $k$ 输出最长的 $k$ 个侵权代码段的信息，包括长度、位置和具体的代码内容。

解题思路

1. 后缀自动机的构建：

   • 为了高效地进行字符串匹配，使用后缀自动机（Suffix Automaton）这一数据结构。后缀自动机是一种用于处理字符串后缀信息的数据结构，它可以在 $O(n)$ 的时间复杂度内构建，并且支持在 $O(m)$ 的时间复杂度内进行字符串匹配，其中 $n$ 是构建自动机的字符串长度，$m$ 是待匹配字符串的长度。
   • 在代码中，通过 SuffixAutomaton 结构体的 sa_extend 方法，逐步将 TDP 代码库中的字符添加到后缀自动机中，完成自动机的构建。

2. 字符串匹配：

   • 利用构建好的后缀自动机，在 JCN 代码库中进行匹配。从 JCN 代码库的第一个字符开始，尝试在后缀自动机中找到与之匹配的路径。
   • 当遇到无法匹配的字符时，通过后缀自动机的 link 指针回溯，直到找到可以继续匹配的状态。
   • 在匹配过程中，记录当前匹配的长度 $l$ 和状态 $v$，并将匹配到的子串信息（包括子串本身、长度、起始位置和结束位置）存储在 InfringingSegment 结构体中，添加到 segments 向量中。

3. 去重和筛选：

   • 由于匹配过程中可能会得到一些重叠或包含关系的子串，需要进行去重和筛选操作，只保留最长的不重叠子串。
   • 首先，对 segments 向量按照子串长度从大到小排序，如果长度相同，则按照起始位置从小到大排序。
   • 然后，使用一个布尔数组 to_keep 标记每个子串是否应该保留。遍历排序后的 segments 向量，对于每个子串，检查它是否被之前的更长子串包含，如果是，则标记为不保留。
   • 最后，根据 to_keep 数组筛选出需要保留的子串，存储在 result 向量中。

4. 输出结果：

   • 对于每个测试用例，根据输入的参数 $k$，输出最长的 $k$ 个侵权代码段的信息，包括长度、位置和具体的代码内容。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <unordered_map>
 
using namespace std;
 
struct State {
    int len, link;
    unordered_map<char, int> next;
};
 
struct SuffixAutomaton {
    vector<State> st;
    int size, last;
 
    SuffixAutomaton() {
        st.push_back({0,  -1, {}});
        size = 1;
        last = 0;
    }
 
    void sa_extend(char c) {
        int p = last;
        int curr = size++;
        st.push_back({st[p].len  + 1, 0, {}});
        while (p >= 0 && st[p].next.find(c)  == st[p].next.end())  {
            st[p].next[c] = curr;
            p = st[p].link;
        }
        if (p == -1) {
            st[curr].link = 0;
        } else {
            int q = st[p].next[c];
            if (st[p].len + 1 == st[q].len) {
                st[curr].link = q;
            } else {
                int clone = size++;
                st.push_back({st[p].len  + 1, st[q].link, st[q].next});
                while (p >= 0 && st[p].next[c] == q) {
                    st[p].next[c] = clone;
                    p = st[p].link;
                }
                st[q].link = clone;
                st[curr].link = clone;
            }
        }
        last = curr;
    }
};
 
struct InfringingSegment {
    string segment;
    int length;
    int position;
    int end_position;
};
 
bool compareSegments(const InfringingSegment &a, const InfringingSegment &b) {
    if (a.length  != b.length)  {
        return a.length  > b.length; 
    } else {
        return a.position  < b.position; 
    }
}
 
vector<InfringingSegment> findInfringingSegments(const string &tdp, const string &jcn) {
    SuffixAutomaton sa;
    for (char c : tdp) {
        sa.sa_extend(c); 
    }
 
    vector<InfringingSegment> segments;
    int n = jcn.size(); 
    int v = 0, l = 0;
    for (int i = 0; i < n; ++i) {
        while (v != 0 && sa.st[v].next.find(jcn[i])  == sa.st[v].next.end())  {
            v = sa.st[v].link; 
            l = sa.st[v].len; 
        }
        if (sa.st[v].next.find(jcn[i])  != sa.st[v].next.end())  {
            v = sa.st[v].next[jcn[i]]; 
            l++;
        }
        if (l > 0) {
            segments.push_back({jcn.substr(i  - l + 1, l), l, i - l + 1, i});
        }
    }
 
    // Remove duplicates and overlapping segments (keep only maximal segments)
    sort(segments.begin(),  segments.end(),  compareSegments);
    vector<bool> to_keep(segments.size(),  true);
    for (int i = 0; i < segments.size();  ++i) {
        if (!to_keep[i]) continue;
        for (int j = i + 1; j < segments.size();  ++j) {
            if (!to_keep[j]) continue;
            // Check if segment j is inside segment i 
            if (segments[j].position >= segments[i].position && 
                segments[j].end_position <= segments[i].end_position) {
                to_keep[j] = false;
            }
        }
    }
 
    vector<InfringingSegment> result;
    for (int i = 0; i < segments.size();  ++i) {
        if (to_keep[i]) {
            result.push_back(segments[i]); 
        }
    }
 
    // Re-sort to ensure order (since some might have been removed)
    sort(result.begin(),  result.end(),  compareSegments);
    return result;
}
 
void processTestCase(int k, const string &tdpCode, const string &jcnCode, int caseNum) {
    vector<InfringingSegment> segments = findInfringingSegments(tdpCode, jcnCode);
    
    cout << "CASE " << caseNum << endl;
    int outputCount = min(k, (int)segments.size()); 
    for (int i = 0; i < outputCount; ++i) {
        const auto &seg = segments[i];
        cout << "INFRINGING SEGMENT " << i + 1 << " LENGTH " << seg.length  << " POSITION " << seg.position  << endl;
        cout << seg.segment  << endl;
    }
}
 
int main() {
    int caseNum = 0;
    while (true) {
        int k;
        cin >> k;
        if (k == 0) break;
        caseNum++;
 
        string line;
        // Read TDP codebase 
        while (getline(cin, line)) {
            if (line == "BEGIN TDP CODEBASE") break;
        }
        string tdpCode;
        while (getline(cin, line)) {
            if (line == "END TDP CODEBASE") break;
            tdpCode += line + "\n";
        }
        // Read JCN codebase 
        while (getline(cin, line)) {
            if (line == "BEGIN JCN CODEBASE") break;
        }
        string jcnCode;
        while (getline(cin, line)) {
            if (line == "END JCN CODEBASE") break;
            jcnCode += line + "\n";
        }
 
        // Remove trailing newlines if any (but according to problem, all characters including newlines are considered)
        processTestCase(k, tdpCode, jcnCode, caseNum);
        cout << endl;
    }
    return 0;
}