HDU 1867（kmp应用）

dejavu1zz

发布于 2020-10-23 15:22:23

2690

发布于 2020-10-23 15:22:23

题意描述

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;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/07/16 ，如有侵权请联系 cloudcommunity@tencent.com 删除

javascript