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

    moyooyoxyzooo
yzoooqyasdfljkamo

Sample Input

abcxxxxabcxabcd abcdxabcxxxxabcx

Sample Output

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

Source

Gold

 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
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);
40 end.     

 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;
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);
70 end.     

0 条评论

相关文章

11910

33330

29640

18030

15720

44530

51220

13550

21440

SQL中GROUP BY用法示例

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

5.1K20