Hdu 2594 Simpsons’ Hidden Talents(Next数组的应用)
程序员文章站
2022-05-02 17:33:10
...
题意:给你两个字符串s1和s2,它们的长度不超过50000,问你s1的前缀和s2的后缀所能匹配的最大长度,如果无法匹配就输出0,否则就输出这个最大长度的序列,并输出它的长度。
分析:拿到这个题感觉很简单,直接将s2字符串拼接到s1字符串后面,然后用Next[新串的长度]的值不就完了吗?这里注意一个地方,例如:s1:abcabc 和 s2:abc,照刚刚那种思路的话就会输出6 但我们很快发现s2的最大长度也才3,所以其实应该输出的是3,所以其实这个长度是不能超过s1和s2的任意一个字符串的长度的。所以我们就不断地利用Next数组的信息,直到要输出的答案不大于两个串中的任意一个的时候,就输出答案。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e4+7;
char s1[maxn<<1],s2[maxn];
int Next[maxn<<1];
int len1,len2,len,ans;
void getNext()
{
int j = -1,i = 0;
Next[0] = -1;
while(i<len)
{
if(j==-1||s1[i]==s1[j])
{
i++;
j++;
Next[i]=j;
}
else j = Next[j];
}
}
void slove()
{
while(ans>len1||ans>len2) ans=Next[ans];
if(!ans) printf("0\n");
else{
s1[ans]='\0';
printf("%s %d\n",s1,ans);
}
}
int main()
{
while(scanf("%s",s1)!=EOF)
{
len1=strlen(s1);
scanf("%s",s2);
len2=strlen(s2);
strcat(s1,s2);
len=strlen(s1);
getNext();
ans = Next[len];
slove();
}
return 0;
}