3409: [Usaco2009 Oct]Barn Echoes 牛棚回声

3409: [Usaco2009 Oct]Barn Echoes 牛棚回声

Time Limit: 3 Sec  Memory Limit: 128 MB

Submit: 57  Solved: 47

[Submit][Status][Discuss]

Description

奶牛们灰常享受在牛栏中哞叫,因为她们可以听到她们哞声的回音。虽然有时候并不能完全听到完整的回音。Bessie曾经是一个出色的秘书,所以她精确地纪录了所有的哞叫声及其回声。她很好奇到底两个声音的重复部份有多长。

输入两个字符串(长度为1到80个字母),表示两个哞叫声。你要确定最长的重复部份的长度。两个字符串的重复部份指的是同时是一个字符串的前缀和另一个字符串的后缀的字符串。

我们通过一个例子来理解题目。考虑下面的两个哞声:

    moyooyoxyzooo
    yzoooqyasdfljkamo

第一个串的最后的部份"yzooo"跟第二个串的第一部份重复。第二个串的最后的部份"mo"跟第一个串的第一部份重复。所以"yzooo"跟"mo"都是这2个串的重复部份。其中,"yzooo"比较长,所以最长的重复部份的长度就是5。

Input

两行: 每一行是1个字符串表示奶牛的哞声或它的回声。

Output

第一行: 包含一个单独的整数表示输入的2个字符串中,一个字符串的前缀和另一个字符串的后缀的最长的重复部份的长度。

Sample Input

abcxxxxabcxabcd abcdxabcxxxxabcx

Sample Output

11 "abcxxxxabcx"是第一个字符串的前缀和第二个字符串的后缀。

HINT

Source

Gold

题解:不知道bzoj啥时候冒出来一堆普及组的题目QAQ

要是想A的话太容易了,所以还是瞎搞搞来连连脑洞吧

方法一:直接\( O\left({N}^{2} \right) \)瞎搞。。。(PS:不要问我为啥只有一层循环,事实上copy的复杂度是O(N)的)

 1 /**************************************************************
 2     Problem: 3409
 3     User: HansBug
 4     Language: Pascal
 5     Result: Accepted
 6     Time:0 ms
 7     Memory:416 kb
 8 ****************************************************************/
 9  
10 var
11    i,j,k,l,m,n:longint;
12    s1,s2,s3:ansistring;
13 function max(x,y:longint):longint;
14          begin
15               if x>y then max:=x else max:=y;
16          end;
17 begin
18      readln(s1);
19      readln(s2);l:=0;
20      for i:=max(length(s2)-length(s1)+1,1) to length(s2) do
21          begin
22               s3:=copy(s2,i,length(s2)+1-i);
23               if copy(s1,1,length(s2)+1-i)=s3 then
24                  begin
25                       l:=length(s2)+1-i;
26                       break;
27                  end;
28          end;
29      for i:=max(length(s1)-length(s2)+1,1) to length(s1) do
30          begin
31               s3:=copy(s1,i,length(s1)+1-i);
32               if copy(s2,1,length(s1)+1-i)=s3 then
33                  begin
34                       l:=max(l,length(s1)+1-i);
35                       break;
36                  end;
37          end;
38      writeln(l);
39      readln;
40 end.     

方法二:这是我第一反应的做法(但是N<=80是什么节奏= =)——字符串哈希(哈希大法好OTL),于是瞎搞搞,很基础的。。。(本人实测N<=3000000都能1s内出来)

 1 /**************************************************************
 2     Problem: 3409
 3     User: HansBug
 4     Language: Pascal
 5     Result: Accepted
 6     Time:0 ms
 7     Memory:4944 kb
 8 ****************************************************************/
 9  
10 const p=314159;q=951413;
11 var
12    i,j,k,l,m,n,x0,y0,x,y:longint;
13    list,a,b:array[0..5000000,1..2] of int64;
14    s1,s2:ansistring;
15 function max(x,y:longint):longint;
16          begin
17               if x>y then max:=x else max:=y;
18          end;
19  
20 begin
21      list[0,1]:=1;list[0,2]:=1;
22      readln(s1);
23      readln(s2);l:=0;
24      n:=max(length(s1),length(s2))+1;
25      for i:=1 to n do
26          begin
27               list[i,1]:=(list[i-1,1]*p) mod q;
28               list[i,2]:=(list[i-1,2]*q) mod p;
29          end;
30      a[0,1]:=0;a[0,2]:=0;
31      for i:=1 to length(s1) do
32          begin
33               a[i,1]:=(a[i-1,1]+(list[i,1]*ord(s1[i])) mod q) mod q;
34               a[i,2]:=(a[i-1,2]+(list[i,2]*ord(s1[i])) mod p) mod p;
35          end;
36      b[0,1]:=0;b[0,2]:=0;
37      for i:=1 to length(s2) do
38          begin
39               b[i,1]:=(b[i-1,1]+(list[i,1]*ord(s2[i])) mod q) mod q;
40               b[i,2]:=(b[i-1,2]+(list[i,2]*ord(s2[i])) mod p) mod p;
41          end;
42      for i:=max(1,length(s1)-length(s2)+1) to length(s1) do
43          begin
44               j:=length(s1)-i+1;
45               x:=(list[i-1,1]*b[j,1]) mod q;
46               y:=(list[i-1,2]*b[j,2]) mod p;
47               x0:=((a[length(s1),1]-a[i-1,1]) mod q+q) mod q;
48               y0:=((a[length(s1),2]-a[i-1,2]) mod p+p) mod p;
49               if (x=x0) and (y=y0) then
50                  begin
51                       l:=j;
52                       break;
53                  end;
54          end;
55      for i:=max(1,length(s2)-length(s1)+1) to length(s2) do
56          begin
57               j:=length(s2)-i+1;
58               x:=(list[i-1,1]*a[j,1]) mod q;
59               y:=(list[i-1,2]*a[j,2]) mod p;
60               x0:=((b[length(s2),1]-b[i-1,1]) mod q+q) mod q;
61               y0:=((b[length(s2),2]-b[i-1,2]) mod p+p) mod p;
62               if (x=x0) and (y=y0) then
63                  begin
64                       l:=max(j,l);
65                       break;
66                  end;
67          end;
68      writeln(l);
69      readln;
70 end.     

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏怀英的自我修炼

考研英语-1-导学

英二图表作文要重视。总体而言,英语一会比英语二难点。不过就写作而言,英语二会比英语一有难度,毕竟图表作文并不好写。

11910
来自专栏钱塘大数据

理工男图解零维到十维空间,烧脑已过度,受不了啦!

让我们从一个点开始,和我们几何意义上的点一样,它没有大小、没有维度。它只是被想象出来的、作为标志一个位置的点。它什么也没有,空间、时间通通不存在,这就是零维度。

33330
来自专栏haifeiWu与他朋友们的专栏

复杂业务下向Mysql导入30万条数据代码优化的踩坑记录

从毕业到现在第一次接触到超过30万条数据导入MySQL的场景(有点low),就是在顺丰公司接入我司EMM产品时需要将AD中的员工数据导入MySQL中,因此楼主负...

29640
来自专栏Ken的杂谈

【系统设置】CentOS 修改机器名

18030
来自专栏腾讯高校合作

【倒计时7天】2018教育部-腾讯公司产学合作协同育人项目申请即将截止!

15720
来自专栏微信公众号:小白课代表

不只是软件,在线也可以免费下载百度文库了。

不管是学生,还是职场员工,下载各种文档几乎是不可避免的,各种XXX.docx,XXX.pptx更是家常便饭,人们最常用的就是百度文库,豆丁文库,道客巴巴这些下载...

44530
来自专栏腾讯社交用户体验设计

ISUX Xcube智能一键生成H5

51220
来自专栏钱塘大数据

中国互联网协会发布:《2018中国互联网发展报告》

在2018中国互联网大会闭幕论坛上,中国互联网协会正式发布《中国互联网发展报告2018》(以下简称《报告》)。《中国互联网发展报告》是由中国互联网协会与中国互联...

13550
来自专栏前端桃园

知识体系解决迷茫的你

最近在星球里群里都有小伙伴说道自己对未来的路比较迷茫,一旦闲下来就不知道自己改干啥,今天我这篇文章就是让你觉得一天给你 25 个小时你都不够用,觉得睡觉都是浪费...

21440
来自专栏FSociety

SQL中GROUP BY用法示例

GROUP BY我们可以先从字面上来理解,GROUP表示分组,BY后面写字段名,就表示根据哪个字段进行分组,如果有用Excel比较多的话,GROUP BY比较类...

5.1K20

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励