牛客:15165 字符串的问题


1.问题描述

题目链接:牛客:15165 字符串的问题
牛客:15165 字符串的问题

2.解题思路

这一题首先我们要把数组中的每一个位置的最大公共真前后缀求出来,放入kmp数组,由于我们不知道要判断多少次,所以使用死循环来解题。我们首先要求的是数组最后一个位置的最大真公共前后缀是否在字符串的非前后缀出现(最后一个位置的最大公共真前后缀为l=kmp[len],len为数组的最后一个元素下标),如果出现则输出该字符串,否则就再求出此次比较的最大真公共前后缀的最大公共前后缀l=kmp[l],如此循环往复,直至l==0说明没有符合条件的子串

3.AC代码

#include<bits/stdc++.h>
using namespace std;
#define max 1000010
char str[max];
int kmp[max];
int main()
{
cin>>str+1;//从数组下标为1开始输入
int len=strlen(str+1);
int j=0;
for(int i=2;i<=len;i++)//for循环是求出最大公共真前后缀
{
while(j>0&&str[j+1]!=str[i])
j=kmp[j];
if(str[j+1]==str[i])
j++;
kmp[i]=j;
}
int l=len;
while(1)
{

l=kmp[l];//l代表整个字符串的真公共前后缀
if(l==0)
{
cout<<"Just a legend";
return 0;
}
int i=2;//每一次l的值改变,意味着要匹配的真公共前后缀要改变
//这时都要从第二个位置进行匹配是否在字符串中除该字符串的真前后缀存外还存在此真公共前后缀所代表的字符串
int j=1;
while(i<len)
{
if(str[i]==str[j])
{
j++;
i++;
}
else
{
j=1;
if(str[i]!=str[j])
i++;
}
if(j>l&&i!=len+1)//i!=len+1是因为出去了整个字符串的公共前后缀
{
for(int k=1;k<=l;k++)
{
cout<<str[k];
}
return 0;
}
}
}
}

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

牛客:15165 字符串的问题

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 牛客:15165 字符串的问题
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏