B - 辛普森一家的隐藏人才(KMP)

简介: B - 辛普森一家的隐藏人才(KMP)

题目:

荷马:玛吉,我刚想办法发现一些我们不知道的人才。

玛吉:是的,它是什么?

荷马:以我为例。我想知道我是否有政治才能,好吗?

玛吉:好的。

荷马:所以我采取一些政治家的名字,克林顿说,并试图找到最长前缀的长度

以克林顿的名字命名,这是我名字中的后缀。这就是我与克林顿这样的政治家有多接近

Marge:为什么选择最长的前缀是后缀???

荷马:嗯,我们的天赋深藏在我们自己里面,Marge。

玛吉:那你有多近?

荷马:0!

玛奇:我并不感到惊讶。

荷马:但是你知道,你必须拥有隐藏在你身边的一些真正的数学天赋。

玛奇:怎么样?

荷马:黎曼和马乔里3分!

Marge:Riemann到底是谁?

荷马:没关系。

编写一个程序,当给定字符串s1和s2时,找到s1的最后一个前缀,即s2的后缀。

input

输入包含两行。第一行包含s1,第二行包含s2。您可以假设所有字母都是小写的。

output

输出由一行组成,其中包含最长字符串,该字符串是s1的前缀和后缀s2,后跟该前缀的长度。如果最长的字符串是空字符串,则输出应为0。

s1和s2的长度最多为50000。

Sample Input

clinton
homer
riemann
marjorie

Sample Output

0
rie 3

解题思路:

这个题让我们求出最长的字符串,该长字符串是s1最后一个前缀,s2最后一个后缀,所以把s1,s2两个字符串连接成一个字符串,然后求出next[]数组,既字符串的长度就是next[ (s1和s2和起来的字符串长度)],注意:可能会出现类似 aaa,aaaaaa 这样的两个字符串,所以我们在输出时要先判断最大长度是否与本身输入字符串大,如果超过了本身字符串长度,就输出两个字符串中较短的那个。

程序代码:

#include<stdio.h>
#include<string.h>
char s[100000],s1[55000],s2[55000];
int n,m,k,next[100000],t,t1;
void get();
int main()
{
  int i,j,l;
  while(scanf("%s%s",s1,s2)!=EOF)
  {
    i=0;j=0;
    n=strlen(s1);
    m=strlen(s2);
    memset(next,0,sizeof(next));
    memset(s,0,sizeof(s));//注意字符串要清零h
    for(i=0;i<n;i++)
      s[i]=s1[i];
    for(j=0;j<m;j++)
      s[i++]=s2[j];
    k=strlen(s);
    get(); 
        
  }
  return 0;
}
void get()
{
  int i=1,j=0;
  int max;
  next[0]=-1;
  while(i<k)
  {
    if(j==-1||s[i]==s[j])
    {
      i++;
      j++;
      next[i]=j;
    }
    else
      j=next[j];
  }
  max=next[k];
  if(max>n) max=n;
  if(max>m) max=m;
  if(max==0)
    printf("%d\n",max);
  else
  {
    for(i=k-max;i<k;i++)
      printf("%c",s[i]);
    printf(" %d\n",max);
  }
  
}
相关文章
|
Web App开发 JavaScript Android开发
iOS SFSafariViewController 获取 Cookies
iOS SFSafariViewController 获取 Cookies
335 0
|
关系型数据库 MySQL 分布式数据库
PolarDB for MySQL优化器查询变换系列 - join条件下推
本篇是PolarDB 优化器查询变换系列的第四篇,之前的文章请见:窗口函数解相关:https://ata.alibaba-inc.com/articles/194578IN-list变换:https://ata.alibaba-inc.com/articles/254779Join消除:https://ata.alibaba-inc.com/articles/252403引言在数据库的查询优化特性
380 0
PolarDB for MySQL优化器查询变换系列 - join条件下推
|
索引
每日三题-下一个排列、颜色分类、寻找重复数
每日三题-下一个排列、颜色分类、寻找重复数
120 0
每日三题-下一个排列、颜色分类、寻找重复数
|
Web App开发 前端开发 测试技术
前端常见兼容问题系列4:sort方法在浏览器中执行效果的差异
sort后面跟着的排序函数,需要返回正数、负数或者0才是标准的影响排序的函数。而采用返回布尔值的函数作为排序函数是一种误用。
3067 0
|
7天前
|
存储 弹性计算 人工智能
【2025云栖精华内容】 打造持续领先,全球覆盖的澎湃算力底座——通用计算产品发布与行业实践专场回顾
2025年9月24日,阿里云弹性计算团队多位产品、技术专家及服务器团队技术专家共同在【2025云栖大会】现场带来了《通用计算产品发布与行业实践》的专场论坛,本论坛聚焦弹性计算多款通用算力产品发布。同时,ECS云服务器安全能力、资源售卖模式、计算AI助手等用户体验关键环节也宣布升级,让用云更简单、更智能。海尔三翼鸟云服务负责人刘建锋先生作为特邀嘉宾,莅临现场分享了关于阿里云ECS g9i推动AIoT平台的场景落地实践。
【2025云栖精华内容】 打造持续领先,全球覆盖的澎湃算力底座——通用计算产品发布与行业实践专场回顾
|
1天前
|
弹性计算 人工智能 安全
云上十五年——「弹性计算十五周年」系列客户故事(第二期)
阿里云弹性计算十五年深耕,以第九代ECS g9i实例引领算力革新。携手海尔三翼鸟、小鹏汽车、微帧科技等企业,实现性能跃升与成本优化,赋能AI、物联网、智能驾驶等前沿场景,共绘云端增长新图景。
|
6天前
|
人工智能 自然语言处理 自动驾驶
关于举办首届全国大学生“启真问智”人工智能模型&智能体大赛决赛的通知
关于举办首届全国大学生“启真问智”人工智能模型&智能体大赛决赛的通知
|
6天前
|
云安全 人工智能 自然语言处理
阿里云x硅基流动:AI安全护栏助力构建可信模型生态
阿里云AI安全护栏:大模型的“智能过滤系统”。
|
Linux 虚拟化 iOS开发
VMware Workstation Pro 25H2 for Windows & Linux - 领先的免费桌面虚拟化软件
VMware Workstation Pro 25H2 for Windows & Linux - 领先的免费桌面虚拟化软件
1110 4