文档章节

hdoj_2594Simpsons’ Hidden Talents

N3verL4nd
 N3verL4nd
发布于 2017/03/25 10:43
字数 649
阅读 5
收藏 0

Simpsons’ Hidden Talents

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1599    Accepted Submission(s): 589


Problem Description
Homer: Marge, I just figured out a way to discover some of the talents we weren’t aware we had.
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.
 

Input
Input consists of two lines. The first line contains s1 and the second line contains s2. You may assume all letters are in lowercase.
 

Output
Output consists of a single line that contains the longest string that is a prefix of s1 and a suffix of s2, followed by the length of that prefix. If the longest such string is the empty string, then the output should be 0.
The lengths of s1 and s2 will be at most 50000.
 

Sample Input

   
clinton homer riemann marjorie
 

Sample Output

   
0 rie 3
利用next数组的性质,以Text[i]结尾的j个字符恰好与pat数组的前j个字符匹配

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<queue>
#include <stack>
using namespace std;
#pragma warning(disable : 4996)
const int MAXN = 50005 * 2;
int Next[MAXN];
char text[MAXN], pat[MAXN];
void get_next()
{
	int i = 0, j = -1;
	int lenp = strlen(pat);
	Next[0] = -1;
	while(i < lenp)
	{
		if(j == -1 || pat[i] == pat[j])
		{
			i++;
			j++;
			Next[i] = j;
		}
		else
		{
			j = Next[j];
		}
	}
}

int main()
{
	freopen("in.txt", "r", stdin);
	int lenp, len;
	while (scanf("%s %s", pat, text) != EOF)
	{
		len = min(strlen(pat), strlen(text));
		memset(Next, 0, sizeof(Next));
		strcat(pat, text);
		lenp = strlen(pat);
		get_next();
		if(Next[lenp] >= len)
		{
			for(int i = 0; i < len; i++)
			{
				printf("%c", pat[i]);
			}
			printf(" %d\n", len);
		}
		else if(Next[lenp] != 0)
		{
			for(int i = 0; i < Next[lenp]; i++)
			{
				printf("%c", pat[i]);
			}
			printf(" %d\n", Next[lenp]);
		}
		else
		{
			printf("0\n");
		}
		
	}
	return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<queue>
#include <stack>
using namespace std;
#pragma warning(disable : 4996)
const int MAXN = 50005;
int Next[MAXN];
int ans[MAXN];
char text[MAXN], pat[MAXN];
void get_next()
{
	int i = 0, j = -1;
	int length = strlen(pat);
	Next[0] = -1;
	while(i < length)
	{
		if(j == -1 || pat[i] == pat[j])
		{
			i++;
			j++;
			Next[i] = j;
		}
		else
		{
			j = Next[j];
		}
	}
}
void kmp()
{
	int lent = strlen(text);
	int lenp = strlen(pat);
	get_next();
	int i = 0, j = 0;
	ans[0] = 0;
	while(i < lent)
	{
		if(j == -1 || text[i] == pat[j])
		{
			i++;
			j++;
			ans[i] = j;
		}
		else
		{
			j = Next[j];
		}
	}
}

int main()
{
	freopen("in.txt", "r", stdin);
	while (scanf("%s %s", pat, text) != EOF)
	{
		int len = strlen(text);
		kmp();	
		if(ans[len] == 0)
		{
			printf("0\n");
		}
		else
		{
			for (int i = 0; i < ans[len]; i++)
			{
				printf("%c", pat[i]);
			}
			printf(" %d\n", ans[len]);
		}

	}
	return 0;
}



© 著作权归作者所有

N3verL4nd
粉丝 1
博文 379
码字总数 481243
作品 0
朝阳
私信 提问
新浪内部对腾讯公司的深度解析报告 [PPT下载]

近日网上流传新浪微博针对腾讯的竞争对手分析报告,主要内容如下: 腾讯的三大主营业务 Tencent’s Core Business 腾讯历年业绩发展数据 Growth of Revenue 腾讯业绩爆发式增长情况分析 Insi...

红薯
2010/10/21
6.5K
29
马太福音和马太效应

昨天,我贴了一首弥尔顿十四行诗的翻译。 这首诗第3行里有这样一个短语: "a talent which is death to hide"。 写成现代英语应该是 "I have a talent, to hide which means death to me" 意......

阮一峰
2006/03/11
0
0
反素数求解及相关题目

反素数 定义:对于任何正整数n,其约数个数记为f(n),例如f(6)=4;如果存在一个正整数n满足:对于任意的正整数x(0

my_sunshine26
2017/05/26
0
0
jQuery 1.4.4 RC2 发布

下载地址:http://code.jquery.com/jquery-1.4.4rc2.js 改动内容和功能增强: (New) Added a new animation method, .fadeToggle() (Enh) Calling .data() with no arguments now includes d......

小编辑
2010/11/04
1K
4
jQuery 1.4.4 正式版发布

下载地址: jQuery Minified (26kb Gzipped) jQuery Regular (179kb) 详细改进内容: (New) Added a new animation method, .fadeToggle() (Enh) Calling .data() with no arguments now in......

红薯
2010/11/12
7.4K
8

没有更多内容

加载失败,请刷新页面

加载更多

Spring Cloud 笔记之Spring cloud config client

观察者模式它的数据的变化是被动的。 观察者模式在java中的实现: package com.hxq.springcloud.springcloudconfigclient;import org.springframework.context.ApplicationListener;i...

xiaoxiao_go
今天
4
0
CentOS7.6中安装使用fcitx框架

内容目录 一、为什么要使用fcitx?二、安装fcitx框架三、安装搜狗输入法 一、为什么要使用fcitx? Gnome3桌面自带的输入法框架为ibus,而在使用ibus时会时不时出现卡顿无法输入的现象。 搜狗和...

技术训练营
今天
4
0
《Designing.Data-Intensive.Applications》笔记 四

第九章 一致性与共识 分布式系统最重要的的抽象之一是共识(consensus):让所有的节点对某件事达成一致。 最终一致性(eventual consistency)只提供较弱的保证,需要探索更高的一致性保证(stro...

丰田破产标志
今天
7
0
docker 使用mysql

1, 进入容器 比如 myslq1 里面进行操作 docker exec -it mysql1 /bin/bash 2. 退出 容器 交互: exit 3. mysql 启动在容器里面,并且 可以本地连接mysql docker run --name mysql1 --env MY...

之渊
今天
7
0
python数据结构

1、字符串及其方法(案例来自Python-100-Days) def main(): str1 = 'hello, world!' # 通过len函数计算字符串的长度 print(len(str1)) # 13 # 获得字符串首字母大写的...

huijue
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部