NOIp2000提高组第三题

题目描述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。

输入输出格式

输入格式：

输入的第一行为一个单独的整数n (n<=20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.

输出格式：

只需输出以此字母开头的最长的“龙”的长度

输入输出样例

输入样例#1：

5attouchcheatchoosetacta

输出样例#1：

23           （连成的“龙”为atoucheatactactouchoose）

思路

　　深搜广搜都可以的，匹配字符串是很基本的编程能力，但是要注意不能自己和自己接龙。程序中有注解。

var a:array[1..1000] of ansistring;    b:array[1..1000] of longint;//b[i]表示第i个字符串被使用了几次，自己是不能和自己接龙的    n:longint;    max:longint=0;    ch:string;procedure init;var i:longint;begin    readln(n);    for i:=1 to n do readln(a[i]);    readln(ch);end;function find(x,y:ansistring):longint;var t:boolean;j,x1,y1:longint;s1,s2:ansistring;begin    find:=0;//对函数操作时一定要注意函数的初始值不一定为零，可能是一些乱七八糟的值，一定要清零。无论他是最值，累加器，累乘器时都应如此。    t:=true;    j:=1;    x1:=length(x);    y1:=length(y);    while (j<=x1) and (j<=y1) and (t) do        begin            s1:=copy(x,x1-j+1,j);            s2:=copy(y,1,j);            if s1=s2 then                begin                    t:=false;                    find:=y1-j;                end;            inc(j);        end;end;procedure main(x:longint;y:ansistring);var k,i:longint;begin    if x>max then max:=x;    for i:=1 to n do        begin            k:=0;            k:=find(y,a[i]);            if (k>0)and(b[i]<2) then                begin                    inc(b[i]);                    main(k+x,a[i]);//深搜加回溯                    dec(b[i]);                end;        end;end;begin    fillchar(b,sizeof(b),0);    init;    main(1,ch);    writeln(max);end.