[USACO 2009 Oct G]Barn Echoes

By way of example, consider two moos: moyooyoxyzooo yzoooqyasdfljkamo The last part of the first string overlaps 'yzooo' with the first part of the second string. The last part of the second string overlaps 'mo' with the first part of the first string. The largest overlap is 'yzooo' whose length is 5.

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 504K, 提交时间: 2020-02-17 21:28:55

#include<bits/stdc++.h>
using namespace std;
string a,b;
int main()
{
	cin>>a>>b;
	int len=a.length();
	for(int x=len-1;x>=0;x--)
	for(int y=0;y<=len-x;y++)
	{
		string c=a.substr(y,x);
		if(b.find(c)!=-1)
		return printf("%d\n",x),0;
	}
	return 0;
}

Pascal(fpc 3.0.2) 解法, 执行用时: 2ms, 内存消耗: 372K, 提交时间: 2019-08-30 12:31:33

var
s1,s2:string;
i,j,z:longint;
begin
readln(s1);
readln(s2);
for i:=length(s1) downto 1 do
 for j:=i to length(s1) do
  if pos(copy(s1,j-i+1,i),s2)<>0 then begin writeln(i); halt; end;
end.

Python3(3.9) 解法, 执行用时: 36ms, 内存消耗: 6808K, 提交时间: 2021-05-05 09:47:04

a, b, ans = input(), input(), 0
for i in range(min(len(a), len(b)),0,-1):
    if a[0:i]==b[len(b)-i:len(b)] or b[0:i]==a[len(a)-i:len(a)]:
        print(i)
        break

详情