HDOJ 4763 - Theme Section 利用KMP的fail数组,,很暴力

网友投稿 1074 2022-10-01

HDOJ 4763 - Theme Section 利用KMP的fail数组,,很暴力

HDOJ 4763 - Theme Section 利用KMP的fail数组,,很暴力

题意:

现在给一个字符串..问订前头..顶后头..中间...不重叠最长的相同串为多长...

题解:

先用KMP得出每个位置的fail值..然后最后一个点开始不断地fail..直到0..标记上这些值..然后从扫描每个位置..每个位置都fail到0..找不冲突.并且最后一个位置fail出现了的.最长的就是答案....

Program:

#include#include#include#include#include#include#include#include#include#include#define MAXN 1000005#define MAXM 1000505#define ll long long #define eps 1e-8using namespace std; char s[MAXN];int fail[MAXN]; void KMP(int len){ int i,h; memset(fail,0,sizeof(fail)); for (i=2;i<=len;i++) { h=fail[i-1]; while (s[h+1]!=s[i] && h) h=fail[h]; if (s[h+1]==s[i]) fail[i]=h+1; else fail[i]=0; } /* for (i=1;i<=len;i++) printf("%d",fail[i]); printf("\n"); */}bool maybe[MAXN];int getans(int len){ int i,h,ans=0; memset(maybe,false,sizeof(maybe)); h=fail[len]; while (h) { maybe[h]=true; h=fail[h]; } for (i=len-1;i>=1;i--) { h=fail[i]; while (h) { if (maybe[h] && i<=len-h && i>=2*h) ans=max(ans,h); h=fail[h]; } } return ans;}int main(){ int cases,len,i; scanf("%d",&cases); while (cases--) { scanf("%s",s+1),len=strlen(s+1); KMP(len); printf("%d\n",getans(len)); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：字符串 字符
上一篇:解决springcloud阿里云OSS文件访问跨域问题的实现
下一篇:gocv(go mod)安装opencv4.5.2 ！！！-Win10环境
相关文章

 发表评论

暂时没有评论，来抢沙发吧~