HDU 2087 HDU 1867 KMP标准模板题

贴两道题，其中HDU2087是中文题，故不解释题目，

思路是，一发KMP，但是特别处理最后一位的失配边为0，这样就可以保证“判断完成但是不多判断”。

第二题，很毒瘤的题，要求求出，给定字符串A,B能够缠到一起组成的子字符串长度“长度较小且字典序较小”的一个。。。。要求，假设str1+str2组成答案，则str1的后缀和str2的前缀中相同的部分，只出现一次。。于是做法就是，两法KMP，特判答案咯。。。然而。。。。此题。。最有难度的地方是读懂提。。。。看了别人的提解读懂得。。。。

2087AC代码：

#include<bits/stdc++.h>

using namespace std;

const long long MAXN=;

long long f[MAXN];

char str1[MAXN];

long long len1;

char str2[MAXN];

long long len2;

bool init()

{

    cin>>str1;

    if(str1[]=='#')return false;

    cin>>str2;

    len1=strlen(str1);

    len2=strlen(str2);

    f[]=;

    f[]=;

    for(int i=;i<len2;++i)

    {

        int j=f[i];

        while(j&&str2[i]!=str2[j])j=f[j];

        f[i+]= str2[i]==str2[j]? j+:;

    }f[len2]=;

    return ;

}

int main()

{

    while(init())

    {

        long long summ=;

        int j=f[];

        for(int i=;i<=len1;++i)

        {

            if(j==len2)summ++;

            while(j&&str1[i]!=str2[j])j=f[j];

            j= str1[i]==str2[j]? j+:;

        }cout<<summ<<"\n";

    }

}

1867AC代码：

#include<bits/stdc++.h>

using namespace std;

const long long MAXN=;

class str

{

    public:

        int f[MAXN];

        char s[MAXN];

        int len;

};

str s1,s2;

string ans1,ans2;

void init()

{

    s1.f[]=;s1.f[]=;

    s2.f[]=;s2.f[]=;

    ans1.clear();

    ans2.clear();

    s1.len=strlen(s1.s);

    s2.len=strlen(s2.s);

    for(int i=;i<s1.len;++i)

    {

        int j=s1.f[i];

        while(j&&s1.s[i]!=s1.s[j])j=s1.f[j];

        s1.f[i+]= s1.s[i]==s1.s[j] ? j+:;

    }

    for(int i=;i<s2.len;++i)

    {

        int j=s2.f[i];

        while(j&&s2.s[i]!=s2.s[j])j=s2.f[j];

        s2.f[i+]= s2.s[i]==s2.s[j] ? j+:;

    }

}

bool com(string &str1,string &str2)

{

    int len=min(str1.length(),str2.length());

    for(int i=;i<len;++i)

    {

        if(str1[i]!=str2[i])

        {

            if(str1[i]<str2[i])break;

            else return false;

        }

    }

    return ;

}

int main()

{

    cin.sync_with_stdio(false);

    while(cin>>s1.s>>s2.s)

    {

        init();

        int j=;

        for(int i=;i<s1.len;++i)

        {

            ans1.push_back(s1.s[i]);

            while(j&&s1.s[i]!=s2.s[j])j=s2.f[j];

            j= s1.s[i]==s2.s[j]? j+:;

        }

        for(;j<s2.len;++j)

        {

            ans1.push_back(s2.s[j]);

        }

        j=;

        for(int i=;i<s2.len;++i)

        {

            ans2.push_back(s2.s[i]);

            while(j&&s2.s[i]!=s1.s[j])j=s1.f[j];

            j= s2.s[i]==s1.s[j]? j+:;

        }

        for(;j<s1.len;++j)

        {

            ans2.push_back(s1.s[j]);

        }

        if(ans1<=ans2&&ans1.length()<=ans2.length())

        {

            cout<<ans1<<"\n";

        }else cout<<ans2<<"\n";

    }

    return ;

}

巴特西

HDU 2087 HDU 1867 KMP标准模板题

最新文章

热门文章