uva 10526 - Intellectual Property(后缀数组)

题目链接:uva 10526 - Intellectual Property

题目大意:给定两个文本,问说下面一个文本中在哪些位置上抄袭了上面个一个文本的,输出n个抄袭位置(不足n个情况全部输出),按照长度优先输出,长度相同的输出位置靠前的。

注意:空格,回车都算一个字符;一段字符只能是抄袭上面的一部分,比如上:NSB*SB 下:NSB 答案:NSB。

解题思路:将两个文本连接在一起,中间用没有出现的字符分割,然后处理处后缀数组,根据height数组的性质,求出哪些位置匹配的长度不为0(注意匹配的位置为后面一段跟前面一段的最大长度),跟据分割符的下标就可以区别前后文本。然后将覆盖的情况处理掉排序输出。

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
const int maxn = 200005;

struct state {
    int pos, len;
    state (int pos = 0, int len = 0) {
        this->pos = pos;
        this->len = len;
    }
};

struct Suffix_Arr {
    int n, s[maxn];
    int SA[maxn], rank[maxn], height[maxn];
    int tmp_one[maxn], tmp_two[maxn], c[maxn];

    void init();
    void add(char* str);
    void build_arr(int m);
    void get_height();
    void solve (int p);
}AC;

inline bool sort_len (const state& a, const state& b) {
    if (a.len != b.len)
        return a.len > b.len;
    return a.pos < b.pos;
}

inline bool sort_pos (const state& a, const state& b) {
    if (a.pos != b.pos)
        return a.pos < b.pos;
    return a.len > b.len;
}

int N, tick;
char str[maxn];

void init () {
    AC.init();

    gets(str);
    while (gets(str) && strcmp(str, "END TDP CODEBASE"))
        AC.add(str);

    AC.s[AC.n++] = 260;
    tick = AC.n;

    gets(str);
    while (gets(str) && strcmp(str, "END JCN CODEBASE"))
        AC.add(str);

    AC.s[AC.n++] = 0;

    AC.build_arr(261);
    AC.get_height();
}

int main () {
    int cas = 0;
    while (~scanf("%d%*c", &N) && N) {

        init();
        if (cas)
            printf("\n");

        printf("CASE %d\n", ++cas);
        AC.solve(tick);
    }
    return 0;
}

void Suffix_Arr::solve(int p) {

    int k = 0;
    memset(c, 0, sizeof(c));

    for (int i = 0; i < n; i++) {
        if (SA[i] < p)
            k = height[i+1];
        else {
            k = min(height[i], k);
            c[i] = max(c[i], k);
        }
    }

    k = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (SA[i] < p) {
            k = height[i];
        } else {
            c[i] = max(c[i], k);
            k = min(height[i], k);
        }
    }

    vector<state> vec, ans;
    for (int i = 0; i < n; i++) {
        if (c[i] >= 1)
            vec.push_back(state(SA[i], c[i]));
    }

    sort(vec.begin(), vec.end(), sort_pos);
    int mv = -1;
    for (int i = 0; i < vec.size(); i++) {
        if (vec[i].pos + vec[i].len <= mv)
            continue;
        ans.push_back(vec[i]);
        mv = vec[i].pos + vec[i].len;
    }

    sort(ans.begin(), ans.end(), sort_len);
    for (int i = 0; i < N && i < ans.size(); i++) {
        printf("INFRINGING SEGMENT %d LENGTH %d POSITION %d\n", i+1, ans[i].len, ans[i].pos - p);
        for (int j = 0; j < ans[i].len; j++)
            printf("%c", s[ans[i].pos + j]);
        printf("\n");
    }
}

void Suffix_Arr::init() {
    n = 0;
    memset(s, 0, sizeof(s));
    memset(height, 0, sizeof(height));
}

void Suffix_Arr::add (char *str) {
    int len = strlen(str);
    for (int i = 0; i < len; i++)
        s[n++] = str[i];
    s[n++] = ‘\n‘;
}

void Suffix_Arr::get_height () {
    for (int i = 0; i < n; i++)
        rank[SA[i]] = i;

    int mv = 0;
    for (int i = 0; i < n - 1; i++) {
        if (mv) mv--;

        int j = SA[rank[i]-1];
        while (s[i+mv] == s[j+mv])
            mv++;
        height[rank[i]] = mv;
    }
}

void Suffix_Arr::build_arr(int m) {
    int *x = tmp_one, *y = tmp_two;

    for (int i = 0; i < m; i++) c[i] = 0;
    for (int i = 0; i < n; i++) c[x[i] = s[i]]++;
    for (int i = 1; i < m; i++) c[i] += c[i-1];
    for (int i = n-1; i >= 0; i--) SA[--c[x[i]]] = i;

    for (int k = 1; k <= n; k <<= 1) {

        int mv = 0;
        for (int i = n - k; i < n; i++) y[mv++] = i;
        for (int i = 0; i < n; i++) if (SA[i] >= k)
            y[mv++] = SA[i] - k;

        for (int i = 0; i < m; i++) c[i] = 0;
        for (int i = 0; i < n; i++) c[x[y[i]]]++;
        for (int i = 1; i < m; i++) c[i] += c[i-1];
        for (int i = n - 1; i >= 0; i--) SA[--c[x[y[i]]]] = y[i];

        swap(x, y);
        mv = 1;
        x[SA[0]] = 0;

        for (int i = 1; i < n; i++)
            x[SA[i]] = (y[SA[i-1]] == y[SA[i]] && y[SA[i-1] + k] == y[SA[i] + k] ? mv - 1 : mv++);

        if (mv >= n)
            break;
        m = mv;
    }
}
时间: 09-04

uva 10526 - Intellectual Property(后缀数组)的相关文章

UVA 12206 - Stammering Aliens(后缀数组)

UVA 12206 - Stammering Aliens 题目链接 题意:给定一个序列,求出出现次数大于m,长度最长的子串的最大下标 思路:后缀数组,搞出height数组后,利用二分去查找即可 这题之前还写过hash的写法也能过,不过写后缀数组的时候,犯了一个傻逼错误,把none输出成node还一直找不到...这是刷题来第二次碰到这种逗比错误了,还是得注意.. 代码: #include <cstdio> #include <cstring> #include <algori

uva 261 - The Window Property(后缀数组)

题目链接:uva 261 - The Window Property 题目大意:给定给一个字符串,枚举子串长度k(len≥k≥1),要求在任意k时,有不超过k+1个不同的子串,如果有的话则输出NO,并且输出最早发现不满足的位置. 解题思路:后缀数组,处理出height数组,对于每个k,遍历height数组,碰到小于k的则分段,将整个height分成若干段,即为有多少种长度为k的不同前缀,需要注意的是要跳过前缀长度不足k的. #include <cstdio> #include <cstr

uva 10829 - L-Gap Substrings(后缀数组)

题目链接:uva 10829 - L-Gap Substrings 题目大意:给定一个字符串,问有多少字符串满足UVU的形式,要求U非空,V的长度为g. 解题思路:对字符串的正序和逆序构建后缀数组,然后枚举U的长度l,每次以长度l分区间,在l和l+d+g所在的两个区间上确定U的最大长度. #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> using nam

uva 12338 - Anti-Rhyme Pairs(后缀数组+RMQ)

题目链接:uva 12338 - Anti-Rhyme Pairs 题目大意:给定若干个字符串,每次询问两个字符串的最长公共前缀. 解题思路:本来应该将每个字符串连接起来做后缀数组,但其实可以直接把一个字符串看成是一个字符,然后排序了就对应是SA数组,然后处理height即可.然后根据后缀数组的性质,字符串i和j的最长公共前缀长度即为rank[i]+1~rank[j]之间height的最小值.特判i=j的情况. #include <cstdio> #include <cstring>

uva 11107 - Life Forms(后缀数组)

题目链接:uva 11107 - Life Forms 题目大意:给定n个字符串,求一个最长的字符串,为n/2个字符串的子串. 解题思路:后缀数组,处理除后缀数组后,二分长度,每次遍历height数组,当长度不足时就分段,如果存在一段中包含n/2个起点,则为可行长度. #include <cstdio> #include <cstring> #include <set> #include <algorithm> using namespace std; co

Uva 12361 File Retrieval 后缀数组+并查集

题意:有F个单词,1 <= F <=60 , 长度<=10^4, 每次可以输入一个字符串,所有包含该字串的单词会形成一个集合. 问最多能形成多少个不同的集合.集合不能为空. 分析:用后缀数组处理.然后首先考虑一个单词形成一个集合的情况,若该单词是其他单词的字串,则该单词显然不会形成一个集合,那么利用后缀数组, 对于每个单词看能否与其他单词有LCP,且LCP 长度为该单词本身长度. 然后就是多个单词形成集合的情况:比较简单的处理方式就是将h数组值相同的下标集中存储,比如h[x] = h[y

poj3294 UVA 11107 Life Forms 后缀数组

http://poj.org/problem?id=3294 Life Forms Time Limit: 5000MS   Memory Limit: 65536K Total Submissions: 9931   Accepted: 2739 Description You may have wondered why most extraterrestrial life forms resemble humans, differing by superficial traits such

uva 11855 - Buzzwords(后缀数组)

题目链接:uva 11855 - Buzzwords 题目大意:给定一个字符串,输出重复子串长度大于1的重复次数(每种长度只算一个次数最多的),并且按照从大到小输出. 解题思路:后缀数组,处理处后缀数组,然后枚举子串长度,按照长度分段即可. #include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; const int max

UVA 11475 Extend to Palindrome(后缀数组+ST表)

[题目链接] http://acm.hust.edu.cn/vjudge/problem/27647 [题目大意] 给出一个字符串,要求在其后面添加最少的字符数,使得其成为一个回文串.并输出这个回文串. [题解] 用拼接符将原字符串倒序相接,做一遍后缀数组,查询两串相应位置的LCP就是以该点为中心的回文串长度的一半分,奇偶求出所有后缀回文串,保留最长的,则补充部分为剩下的前缀的倒置.至于查询两串的LCP我们可以在height数组建立ST表查询. [代码] #include <cstdio> #