(ssl1463)公共子串

公共子串

Time Limit:1000MS  Memory Limit:65536K Total Submit:198 Accepted:113

Description

设有A、B两个字符串，找出A、B共同子串，每个字符串无相同字符，可以不连续，但顺序不能颠倒。

Input

第一行字符串A  第二行字符串Ｂ 

Output

最长公共子串的长度.

Sample Input

abcfbc abfcab

Sample Output

4

Source

elba

var s,ss:string; f:array[0..1000,0..1000] of longint; i,j,len,len2:longint; function max(a,b:longint):longint;//状态转移方程 begin if a>b then exit(a); exit(b); end; begin readln(s); read(ss); len:=length(s); len2:=length(ss); for i:=1 to len do for j:=1 to len2 do if s[i]=ss[j] then f[i,j]:=f[i-1,j-1]+1//如果它相同的话，那么公共字串的长度就是上一个加上它 else f[i,j]:=max(f[i-1,j],f[i,j-1]);//如果反之，那么它就继承之前最大的长度 writeln(f[len,len2])//到了最后，也就全都汇集在末尾 end.