欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

Simpsons’ Hidden Talents HDU - 2594(kmp的应用)

程序员文章站 2022-04-14 11:18:06
Simpsons’ Hidden Talents HDU - 2594题意:给你两个串s1,s2 。要你求第一个串s1的前缀 等于 s2的最长。且要最长。思路1:把两串合并,就是求next了。不过注意,求完后的长度要小于len1和len2.思路2:利用kmp去求。把s1当成模式串。之后去匹配第二个串,返回值为jjj的值.AC1(思路1,char)#include #include using namespace std...

Simpsons’ Hidden Talents HDU - 2594

题意:

给你两个串s1,s2 。要你求第一个串s1的前缀 等于 s2的最长。
且要最长。

思路1:

  1. 把两串合并,就是求next了。
  2. 不过注意,求完后的长度要小于len1和len2.

思路2:

利用kmp去求。把s1当成模式串。之后去匹配第二个串,返回值为 j j j的值.

AC1(思路1,char)

#include <iostream>
#include <cstring>
using namespace std;
const int maxn=5e4+10;
char s1[maxn],s2[maxn],s[maxn*2];
int nxt[maxn*2];
void getnxt(char *p){
    int m=strlen(p);
    int i=0,j=-1;
    nxt[0]=-1;
    while(i<m){
        if(j==-1||p[i]==p[j])nxt[++i]=++j;
        else j=nxt[j];
    }
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    while(cin>>s1>>s2){
       //cin>>s2;
        strcpy(s,"");
        strcat(s,s1);
        //cout<<s<<endl;
        strcat(s,s2);
        getnxt(s);
        int len=strlen(s), len1=strlen(s1),len2=strlen(s2);
        while(nxt[len]>len1||nxt[len]>len2)len=nxt[len];///没加小于len2,qwq
        if(nxt[len]<=0)cout<<0<<endl;
        else {
            for(int i=0; i<nxt[len]; i++)cout<<s[i];
            cout<<' '<<nxt[len]<<endl;
        }
    }
    return 0;
}

AC2(思路1,string)

#include <iostream>
#include <string>
using namespace std;
const int maxn=1e5+10;
int nxt[maxn];
void getnxt(string p){
    int m=p.size();
    int i=0, j=-1;
    nxt[0]=-1;
    while(i<m){
        if(j==-1||p[i]==p[j])nxt[++i]=++j;
        else j=nxt[j];
    }
}
int main()
{
    string s1,s2;
    while(cin>>s1>>s2){
        int len1=s1.size(),len2=s2.size();
        s1+=s2;
        //cout<<s1<<endl;
        getnxt(s1);
        int len=s1.size();
        while(nxt[len]>len1||nxt[len]>len2)len=nxt[len];
        if(nxt[len]==0)cout<<0<<endl;
        else {
            for(int i=0; i<nxt[len]; i++)cout<<s1[i];
            cout<<' '<<nxt[len]<<endl;
        }
    }
    return 0;
}

AC3(思路2,char)

#include <iostream>
#include <cstring>
using namespace std;
const int maxn=5e4+10;
char s[maxn],p[maxn];
int nxt[maxn];
void getnxt(char *p){
    int i=0,j=-1;
    int m = strlen(p);
    nxt[0]=-1;
    while(i<m){
        if(j==-1||p[i]==p[j])nxt[++i]=++j;
        else j=nxt[j];
    }
}
int kmp(char *s,char *p){
    int i=0,j=0;
    int n = strlen(s), m = strlen(p);
    while(i<n){
        if(j==-1||s[i]==p[j])i++,j++;
        else j=nxt[j];
    }
    return j;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    while(cin>>p>>s){
        getnxt(p);
        int res=kmp(s,p);
        if(res==0)cout<<0<<endl;
        else {
            for(int i=0; i<res; i++)cout<<p[i];
            cout<<" "<<res<<endl;
        }
    }
    return 0;
}

本文地址:https://blog.csdn.net/qq_45377553/article/details/108979653

相关标签: # kmp