Simpsons’ Hidden Talents
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1746 Accepted Submission(s): 637
Marge: Yeah, what is it?
Homer: Take me for example. I want to find out if I have a talent in politics, OK?
Marge: OK.
Homer: So I take some politician’s name, say Clinton, and try to find the length of the longest prefix
in Clinton’s name that is a suffix in my name. That’s how close I am to being a politician like Clinton
Marge: Why on earth choose the longest prefix that is a suffix???
Homer: Well, our talents are deeply hidden within ourselves, Marge.
Marge: So how close are you?
Homer: 0!
Marge: I’m not surprised.
Homer: But you know, you must have some real math talent hidden deep in you.
Marge: How come?
Homer: Riemann and Marjorie gives 3!!!
Marge: Who the heck is Riemann?
Homer: Never mind.
Write a program that, when given strings s1 and s2, finds the longest prefix of s1 that is a suffix of s2.
The lengths of s1 and s2 will be at most 50000.
homer
riemann
marjorie
rie 3
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define MAXN 50050
char str[MAXN],pass[MAXN];
int next[MAXN],strnum,passlen;
void getnext()
{
int i,j;
next[0]=next[1]=0;
for(i=1,j=0;i<passlen;i++)
{
j=next[i];
while(j&&pass[i]!=pass[j])
{
j=next[j];
}
next[i+1]=pass[i]==pass[j]?j+1:0;
}
/*
for(i=0;i<passlen;i++)
{
printf("%d ",next[i]);
}*/
}
int main()
{
int i,j;
while(scanf("%s%s",pass,str)!=EOF)
{
strnum=strlen(str);
passlen=strlen(pass);
getnext();
for(i=0,j=0;i<strnum;i++)
{
while(j&&str[i]!=pass[j])
{
j=next[j];
}
if(str[i]==pass[j])
{
j++;
}
} if(j)
printf("%s %d\n",str+strnum-j,j);
else
{
printf("0\n");
}
} return 0;
}
hdu2594 Simpsons’ Hidden Talents kmp的更多相关文章
-
HDU2594 Simpsons’ Hidden Talents —— KMP next数组
题目链接:https://vjudge.net/problem/HDU-2594 Simpsons’ Hidden Talents Time Limit: 2000/1000 MS (Java/Oth ...
-
HDU2594 Simpsons’ Hidden Talents 【KMP】
Simpsons' Hidden Talents Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java ...
-
hdu 2594 Simpsons’ Hidden Talents KMP
Simpsons’ Hidden Talents Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java ...
-
hdu 2594 Simpsons’ Hidden Talents KMP应用
Simpsons’ Hidden Talents Problem Description Write a program that, when given strings s1 and s2, fin ...
-
hdu2594 Simpsons&#39; Hidden Talents【next数组应用】
Simpsons’ Hidden Talents Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java ...
-
hdu 2594 Simpsons’ Hidden Talents(KMP入门)
Simpsons’ Hidden Talents Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java ...
-
hdu2594 Simpsons’ Hidden Talents LCS--扩展KMP
Homer: Marge, I just figured out a way to discover some of the talents we weren’t aware we had.Marge ...
-
kuangbin专题十六 KMP&;&;扩展KMP HDU2594 Simpsons’ Hidden Talents
Homer: Marge, I just figured out a way to discover some of the talents we weren’t aware we had. Marg ...
-
HDU2594——Simpsons’ Hidden Talents
Problem Description Homer: Marge, I just figured out a way to discover some of the talents we weren’ ...
随机推荐
-
VMware虚拟机无法ping通/分配虚拟IP/远程访问的问题的解决方案:
最近老板要写俩web系统,没有自己的服务器,没办法,只好先借用下学院的服务器做下测试调试.那好,问题来了~ 学院的服务器不是我一个人在维护,经常有其他人登进登出(!!!担心文件丢失啊!!!),硬伤!! ...
-
Oracle decode()函数应用
在项目第一次遇到decode()函数,简单写一下用法. ')), ')), ')), ')), ')), ')), ')) from wg_jzmb jz, wg_jzfz fz where jz.s ...
-
android WebView网页浏览器
组件位置:composite>WebView .xml <WebView android:id="@+id/webview_pipeweb" android:layou ...
-
html+css二级菜单制作!
二级菜单!!<!DOCTYPE html<html lang="e<head> <meta charset="UTF-8"> < ...
-
BZOJ3776 : 警察局
怎么3776又换题目了…换题目了…题目了…目了…了… SCC缩点后只有入度或者出度为0的点必须要放警察局 假设一共有t-1个入度或者出度为0的SCC q[1]-q[t-1]表示这些SCC中点的个数 q ...
-
App开发需要了解的基本技术
本文针对小白用户对App做一个简单的介绍,首先要了解App都有哪些类型,不同的类型适用于哪些需求,用户可以根据自己的需求选择不同的App开发. 一 App有哪些形式 WebApp:简单来说,Web A ...
-
SQLite3基本使用从shell到python
SQLite是一个轻量级的关系型数据库,在訪问量不超过10万PV的中小站点中使用绰绰有余. 并且使用方便,接口简单,以下从命令行和python接口双方面介绍SQLite3的基本操作. 在linux终端 ...
-
Android MediaPlayer Error -1004
之前用Android自带的VideoView播放在线视频一直没问题的.今天突然碰到无法播放. MediaPalyer返回的错误代码是-1004,API文档上写的是:Bitstream is not c ...
-
记录下扣jio的2018年
踩着18年的尾巴,写下这篇总结,既给18年画上句号,也展望19年,制定下计划. 自17年底正式接手团队项目管理工作以来,虽然前面一年都干了大部分工作,但正式走到这个位置上来,还是有一部分的期待.接手之 ...
-
HTML 部分非常用标签
标签 描述 示例 <!DOCTYPE> 定义文档类型. HTML5 : <!DOCTYPE html> HTML4.* :<!DOCTYPE HTML PUBLIC & ...