`
暴风雪
  • 浏览: 389069 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
社区版块
存档分类
最新评论

[多字符串匹配-后缀数组]poj 3450:Corporate Identity

阅读更多

大致题意:
    给你n个字符串,求出这n个字符串的最长公共子串。注意这里最长公共子串不是DP里面的LCS,这里必须要连续。

 

大致思路:

    后缀数组的典型运用。首先把这些字符串相连在一起,中间用分隔符隔开,二分枚举公共子串长度。查看是否存在相邻的个后缀,他们分别属于n个字符串,且它们之间的最长公共前缀长度(height)大于枚举的长度

 

 

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax = 200001;

int  num[nMax];
int sa[nMax], rank[nMax], height[nMax];
int wa[nMax], wb[nMax], wv[nMax], wd[nMax];

int cmp(int *r, int a, int b, int l){
    return r[a] == r[b] && r[a+l] == r[b+l];
}

void da(int *r, int n, int m){          //  倍增算法 r为待匹配数组  n为总长度 m为字符范围
    int i, j, p, *x = wa, *y = wb, *t;
    for(i = 0; i < m; i ++) wd[i] = 0;
    for(i = 0; i < n; i ++) wd[x[i]=r[i]] ++;
    for(i = 1; i < m; i ++) wd[i] += wd[i-1];
    for(i = n-1; i >= 0; i --) sa[-- wd[x[i]]] = i;
    for(j = 1, p = 1; p < n; j *= 2, m = p){
        for(p = 0, i = n-j; i < n; i ++) y[p ++] = i;
        for(i = 0; i < n; i ++) if(sa[i] >= j) y[p ++] = sa[i] - j;
        for(i = 0; i < n; i ++) wv[i] = x[y[i]];
        for(i = 0; i < m; i ++) wd[i] = 0;
        for(i = 0; i < n; i ++) wd[wv[i]] ++;
        for(i = 1; i < m; i ++) wd[i] += wd[i-1];
        for(i = n-1; i >= 0; i --) sa[-- wd[wv[i]]] = y[i];
        for(t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i ++){
            x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p - 1: p ++;
        }
    }
}

void calHeight(int *r, int n){           //  求height数组。
    int i, j, k = 0;
    for(i = 1; i <= n; i ++) rank[sa[i]] = i;
    for(i = 0; i < n; height[rank[i ++]] = k){
        for(k ? k -- : 0, j = sa[rank[i]-1]; r[i+k] == r[j+k]; k ++);
    }
}

int loc[nMax],m;
char str[nMax],res[nMax];
bool vis[1004];

bool check(int mid,int len){
    int i,j,tot;
    tot=0;
    memset(vis,0,sizeof(vis));
    for(i=2;i<=len;i++){
        if(height[i]<mid){
            memset(vis,0,sizeof(vis));
            tot=0;
        }
        else{
            if(!vis[loc[sa[i-1]]]){
                vis[loc[sa[i-1]]]=1;
                tot++;
            }
            if(!vis[loc[sa[i]]]){
                vis[loc[sa[i]]]=1;
                tot++;
            }
            if(tot==m){
                for(j=0;j<mid;j++){
                    res[j]=num[sa[i]+j]+'a'-1;
                }res[mid]='\0';
                return 1;
            }
        }
    }
    return 0;
}

int main(){
    int n,k,i,j,a,b,sp,ans;
    while(scanf("%d",&m)&&m){
        sp=29;    //分隔符
        n=0;
        ans=0;
        for(i=1;i<=m;i++){
            scanf("%s",str);
            for(j=0;str[j];j++){
                loc[n]=i;
                num[n++]=str[j]-'a'+1;
            }
            loc[n]=sp;
            num[n++]=sp++;
        }
        num[n]=0;
        da(num, n + 1, sp);
        calHeight(num,n);
        int left=0,right=strlen(str),mid;//开始二分
        while(right>=left){
            mid=(right+left)/2;
            if(check(mid,n)){         //判断长度为mid的串是否是所有字符串的公共子串
                left=mid+1;
                ans=mid;
            }
            else{
                right=mid-1;
            }
        }
        if(ans!=0){
            printf("%s\n",res);
        }
        else{
            printf("IDENTITY LOST\n");
        }
    }
    return 0;
}
0
0
分享到:
评论

相关推荐

    经典 的POJ 分类

    - POJ 3349、POJ 3274:字符串匹配及Hash应用。 - POJ 2151、POJ 1840:利用Hash进行快速查询。 - POJ 2002、POJ 2503:Hash表在实际问题中的运用。 ### 搜索算法 #### 深度优先搜索 (DFS) - **题目示例**: -...

    acm新手训练方案新手必备

    - **字符串算法**:包括后缀数组、AC自动机等。 - **组合优化**:涉及组合优化问题的求解方法。 - **数学建模**:学习如何将实际问题转化为数学模型进行求解。 - **数论算法**:包括质因数分解、扩展欧几里得算法等...

    初学者练题开始------在POJ上(注:是百练)

    - **子串**(4.4 例题):字符串查找和匹配,可以采用KMP、Boyer-Moore或Rabin-Karp算法。 - **字符串判等**(4.1 练习题):学习如何比较两个字符串是否相等,理解字符串的比较操作。 4. **日期与时间**: - **...

    acm训练计划(poj的题)

    - (poj1961, poj2406):高效的字符串匹配算法。 ### 十、进阶状态压缩 1. **状态压缩技巧**: - 如何高效地表示和压缩状态。 2. **状态压缩优化**: - (poj3411, poj1724):进一步提高状态压缩动态规划的效率...

    后缀数组相关题解1

    后缀数组在此问题中的应用主要是通过计算字符串的最长公共前后缀来确定可能的主题,并结合转调的概念进行匹配。 【POJ 3261】则是一个关于子串重复的问题,我们需要找到能重复K次的最长不重叠子串。这里可以利用...

    POJ 分类题目

    - **定义**:字符串处理技术,包括字符串匹配算法等。 - **示例题目**: - poj1035 - poj3080 - poj1936 - **应用场景**:适用于文本处理、模式匹配等问题。 **2. 排序** - **定义**:包括快速排序、归并排序、...

    ACM POJ PKU 最全题目分类

    ### ACM POJ PKU 最全题目分类解析 #### 动态规划(DP) 在计算机科学领域,动态规划(Dynamic Programming, DP)是一种重要的算法思想,主要用于解决多阶段决策过程中的优化问题。它通过将原问题分解成相互重叠的...

    poj(PKU-2314-POJ language

    根据提供的文件信息,我们可以分析出该段代码是用于解决POJ平台上的2314题的一种解决方案,主要涉及到了变量管理、表达式处理等方面。下面将详细解释代码中的关键概念和实现逻辑。 ### 关键概念解析 #### Variable...

    ACM 题型

    - 示例题目:poj1191, poj1054, poj3280, poj2029, poj2948, poj1925, poj3034 2. **四边形不等式** - 示例题目:POJ3254, poj2411, poj1185 3. **记忆化搜索** - 示例题目:poj2057, poj1947, poj2486, poj...

    acm新手刷题攻略之poj

    - 字符串匹配算法如KMP算法可以提高字符串匹配的效率。 以上列举的题目只是冰山一角,POJ上还有更多类型的题目等待着大家去探索。通过不断练习这些题目,可以逐渐建立起解决各类问题的能力,为参加更高级别的竞赛...

    ACM题目分类.txt

    - **描述**:字符串处理技术包括字符串匹配、正则表达式等。 - **应用场景**:文本检索、模式匹配等。 - **相关题目**: - POJ 2388 - POJ 2299 #### 3. 哈希表 - **描述**:哈希表是一种基于数组实现的高效数据...

    ACM北大训练

    - poj1035: 涉及字符串操作和模式匹配问题。 ##### 2. 排序 - **定义**: 包括快速排序、归并排序和堆排序等,用于将数据按照一定顺序排列。 - **应用场景**: 应用于几乎所有需要对数据进行排序的场景。 - **示例...

    poj训练计划.doc

    - 字符串处理:如KMP算法和后缀数组,用于字符串搜索和模式匹配,如`poj1035, poj3080`。 - 排序算法:如快速排序和归并排序,用于对数据进行排序,如`poj2388, poj2299`。 - 并查集:用于处理集合的合并和查询...

    树状数组练习:POJ 2481(JAVA)

    【标题】"树状数组练习:POJ 2481(JAVA)" 是一篇关于使用树状数组(也称为线段树)解决编程竞赛问题的文章。这篇文章可能详细讲解了如何运用这种数据结构来解决特定的问题POJ 2481。POJ(Programming Online Judge)...

    string-problem(POJ).rar_POJ 19_poj

    综上所述,这个压缩包内的资料涵盖了字符串处理的多个方面,包括但不限于基本操作、模式匹配算法、字符串排序、编辑距离计算以及数据压缩。对于学习和提升在ACM竞赛中处理字符串问题的能力来说,这是一个宝贵的资源...

    poj3261.zip_POJ 3261

    在POJ 3261的解题过程中,我们可能需要用到后缀数组的特性,比如求解字符串的最长重复子串,或者查找某个子串出现的所有位置。这些问题都可以通过比较后缀数组中的相邻元素之间的关系来解决。 在给出的压缩文件`poj...

    树状数组练习:POJ 3067

    【标题】"树状数组练习:POJ 3067" 树状数组,也称为线段树(Segment Tree),是一种高效的数据结构,用于处理区间查询和修改问题。在这个问题中,我们通过分析POJ 3067的题目来探讨如何应用树状数组解决实际问题。...

    滚动数组应用:POJ 1159

    标题“滚动数组应用:POJ 1159”指的是一个关于编程竞赛问题的解决方案,该问题在POJ(Programming Online Judge)平台上被提出。滚动数组是一种优化动态规划算法的技术,通过巧妙地重用和更新已经计算过的状态,减少...

    西北工业大学-c语言-POJ-题目及答案-第七季.doc

    该文档提供了西北工业大学 POJ(Programming Online Judge)平台上的 C 语言编程题目及答案,共计 7 题,涵盖了基本数据类型、运算符、控制结构、函数和数组等 C 语言知识点。 知识点一:基本数据类型 * 整数类型...

    poj pku图论、网络流入门题总结、汇总

    根据提供的标题“poj pku图论、网络流入门题总结、汇总”及描述“很经典的图论,网络流入门的题目,值得一看啊~~其中有简单的解析”,本篇将对这些经典图论与网络流问题进行详细的分析和总结。通过梳理各题目及其...

Global site tag (gtag.js) - Google Analytics