牛客 Barn Echoes(扩展KMP)

发表于 | 阅读次数：

题目链接

题意

给出两个字符串，求一个字符串的前缀与另一个字符串的后缀最长重叠长度

分析

采用扩展KMP可以轻松解决此题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>
using namespace std;
string str1,str2,s1,s2;
//设从i位置开始的s的后缀串为s0i
void z_function(string s,int n,int z[])//扩展KMP(Z函数),求s与s0i的最长公共前缀的长度
{
    for(int i=0 ;i<n ;i++)
        z[i]=0;
    for(int i=1,l=0,r=0; i<n ; i++)
    {
        if(i<=r)
            z[i]=min(r-i+1,z[i-l]);
        while(i+z[i]<n&&s[z[i]]==s[i+z[i]])
            ++z[i];
        if(i+z[i]-1>r)
        {
            l=i;
            r=i+z[i]-1;
        }
    }
}
int main()
{
    int z1[200]={},z2[200]={};
    cin>>str1>>str2;
    int str1_len=str1.size(),str2_len = str2.size();
    s1=str1+str2;
    s2 = str2 +str1;
    z_function(s1,s1.size(),z1);
    int len1=s1.size(),ans=0;
    for(int i=str1_len ;i<len1;i++)
    {
        if(z1[i]==len1-i)
        {
            ans=len1-i;
            break;
        }
    }
    z_function(s2,s2.size(),z2);
    int len2  = len1;
    for(int i=str2_len ;i<len2;i++)
    {
        if(z2[i]==len2-i)
        {
            ans=max(ans,len2-i);
            break;
        }
    }
    printf("%d\n",ans);

    return 0;
}
0%