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
abcdxabcxxxxabcx
Sample Output
11
"abcxxxxabcx"是第一个字符串的前缀和第二个字符串的后缀。
HINT
Source
题解：不知道bzoj啥时候冒出来一堆普及组的题目QAQ
要是想A的话太容易了，所以还是瞎搞搞来连连脑洞吧
方法一：直接\( O\left({N}^{2} \right) \)瞎搞。。。（PS：不要问我为啥只有一层循环，事实上copy的复杂度是O(N)的）
/**************************************************************
Problem:
User: HansBug
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/ var
i,j,k,l,m,n:longint;
s1,s2,s3:ansistring;
function max(x,y:longint):longint;
begin
if x>y then max:=x else max:=y;
end;
begin
readln(s1);
readln(s2);l:=;
for i:=max(length(s2)-length(s1)+,) to length(s2) do
begin
s3:=copy(s2,i,length(s2)+-i);
if copy(s1,,length(s2)+-i)=s3 then
begin
l:=length(s2)+-i;
break;
end;
end;
for i:=max(length(s1)-length(s2)+,) to length(s1) do
begin
s3:=copy(s1,i,length(s1)+-i);
if copy(s2,,length(s1)+-i)=s3 then
begin
l:=max(l,length(s1)+-i);
break;
end;
end;
writeln(l);
readln;
end.
方法二：这是我第一反应的做法（但是N<=80是什么节奏= =）——字符串哈希（哈希大法好OTL），于是瞎搞搞，很基础的。。。（本人实测N<=3000000都能1s内出来）
/**************************************************************
Problem:
User: HansBug
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/ const p=;q=;
var
i,j,k,l,m,n,x0,y0,x,y:longint;
list,a,b:array[..,..] of int64;
s1,s2:ansistring;
function max(x,y:longint):longint;
begin
if x>y then max:=x else max:=y;
end; begin
list[,]:=;list[,]:=;
readln(s1);
readln(s2);l:=;
n:=max(length(s1),length(s2))+;
for i:= to n do
begin
list[i,]:=(list[i-,]*p) mod q;
list[i,]:=(list[i-,]*q) mod p;
end;
a[,]:=;a[,]:=;
for i:= to length(s1) do
begin
a[i,]:=(a[i-,]+(list[i,]*ord(s1[i])) mod q) mod q;
a[i,]:=(a[i-,]+(list[i,]*ord(s1[i])) mod p) mod p;
end;
b[,]:=;b[,]:=;
for i:= to length(s2) do
begin
b[i,]:=(b[i-,]+(list[i,]*ord(s2[i])) mod q) mod q;
b[i,]:=(b[i-,]+(list[i,]*ord(s2[i])) mod p) mod p;
end;
for i:=max(,length(s1)-length(s2)+) to length(s1) do
begin
j:=length(s1)-i+;
x:=(list[i-,]*b[j,]) mod q;
y:=(list[i-,]*b[j,]) mod p;
x0:=((a[length(s1),]-a[i-,]) mod q+q) mod q;
y0:=((a[length(s1),]-a[i-,]) mod p+p) mod p;
if (x=x0) and (y=y0) then
begin
l:=j;
break;
end;
end;
for i:=max(,length(s2)-length(s1)+) to length(s2) do
begin
j:=length(s2)-i+;
x:=(list[i-,]*a[j,]) mod q;
y:=(list[i-,]*a[j,]) mod p;
x0:=((b[length(s2),]-b[i-,]) mod q+q) mod q;
y0:=((b[length(s2),]-b[i-,]) mod p+p) mod p;
if (x=x0) and (y=y0) then
begin
l:=max(j,l);
break;
end;
end;
writeln(l);
readln;
end.