专栏首页奇妙的算法世界HDU 1867(kmp应用)

HDU 1867(kmp应用)

题意描述

Generally speaking, there are a lot of problems about strings processing. Now you encounter another such problem. If you get two strings, such as “asdf” and “sdfg”, the result of the addition between them is “asdfg”, for “sdf” is the tail substring of “asdf” and the head substring of the “sdfg” . However, the result comes as “asdfghjk”, when you have to add “asdf” and “ghjk” and guarantee the shortest string first, then the minimum lexicographic second, the same rules for other additions.

思路

使用两次kmp,分别求出p匹配s和s匹配p的相同前后缀的个数,如果相同,则使用strcpy()来比较两个字符串的字典序大小,否则按照题意输出

AC代码

#include<bits/stdc++.h>
#define x first
#define y second
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long LL;
const int N=2*1e5+10;
const int M=150;
const int INF=0x3f3f3f3f;
const int MOD=998244353;
int n,m,ne[N];
char p[N],s[N];
void get_next(char* str){
    int len=strlen(str);
    int i=0,j=-1;
    ne[0]=-1;
    while(i<len){
        if(j==-1 || str[i]==str[j]){
            i++;
            j++;
            ne[i]=j;
        }else{
            j=ne[j];
        }
    }
}
int get_kmp(char* str1,char* str2){
    int len1=strlen(str1);
    int len2=strlen(str2);
    get_next(str2);
    int i=0,j=0;
    while(i<len1){
        if(j==-1 || str1[i]==str2[j]){
            i++;
            j++;
        }else{
            j=ne[j];
        }
    }
    return j;
}
void solve(){
    while(scanf("%s%s",s,p)!=EOF){
        int k1=get_kmp(p,s);
        int k2=get_kmp(s,p);
        if(k1>k2){
            printf("%s%s",p,s+k1);
        }else if(k1<k2){
            printf("%s%s",s,p+k2);
        }else{
            if(strcmp(s,p)>0) printf("%s%s",p,s+k2);
            else if(strcmp(s,p)<0) printf("%s%s",s,p+k2);
            else printf("%s",p);
        }
        puts("");
    }
}
int main(){
    //IOS;
    solve();
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • codeforces 1066B(树)

    Ramesses knows a lot about problems involving trees (undirected connected graphs...

    dejavu1zz
  • codeforces 1077D(二分)

    dejavu1zz
  • codeforces 1312C(思维)

    给定n和k,输入n个数字,每次可以让第i个数字减去k的x次幂,每个x只能用一次,问能否将全部数字变为0

    dejavu1zz
  • 洛谷P3924 康娜的线段树(期望 前缀和)

    如果你和我一样为了AC不追求效率的话直接#define int __int128就行了。。

    attack
  • 2019 CCPC 重现赛 1006 基环树

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    用户2965768
  • C++ 隐式类型转换

    C++定义了一组内置类型对象之间的转换标准,在必要的时候它们被编译器隐式的转换 1、任何两种或多种类型的数据和变量混合操作的时候,最宽的数据类型成为目标转换类型...

    用户1215536
  • POJ3683 Priest John's Busiest Day(2-SAT)

    Description John is the only priest in his town. September 1st is the John's bu...

    attack
  • mser 最大稳定极值区域(文字区域定位)算法 附完整C代码

    mser 的全称:Maximally Stable Extremal Regions 第一次听说这个算法时,是来自当时部门的一个同事, 提及到他的项目用它来做文...

    cpuimage
  • POJ 2104 K-th Number(主席树)

    Description You are working for Macrohard company in data structures department...

    attack
  • LOJ#121. 「离线可过」动态图连通性(线段树分治)

    我们用线段树维护。线段树的每个节点维护一个vector表示覆盖了当前节点的边的存在区间

    attack

扫码关注云+社区

领取腾讯云代金券