Pro_5.Pas 2.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596
  1. Program Pro_5; {例5的动态规划解法}
  2. Const
  3. Datafile ='Data.Txt'; {文本输入文件名}
  4. Inputfile ='Input.Txt'; {基元输入文件名}
  5. Outputfile ='Output.Txt'; {输出文件名}
  6. Type
  7. Jis =Record {基元记录类型说明}
  8. Lst:Byte; {基元长度}
  9. St:String[20]; {基元内容}
  10. End;
  11. Var
  12. F :Text; {文件变量}
  13. Ji :Array[1..100] Of Jis; {基元记录数组}
  14. Ch :Array[0..21] Of Char; {字符记录数组}
  15. Bo :Array[0..21] Of Boolean; {记录是否为前缀的数组}
  16. N :Integer; {基元数目}
  17. Tot :Longint; {总的字符数}
  18. Big :Longint; {最长的前缀长度}
  19. Procedure Init; {初始化过程}
  20. Var
  21. I :Integer;
  22. Begin
  23. Assign(F,Inputfile);
  24. Reset(F);
  25. Readln(F,N); {读入每个基元}
  26. For I:=1 To N Do
  27. Begin
  28. Readln(F,Ji[I].Lst);
  29. Readln(F,Ji[I].St);
  30. End;
  31. Close(F);
  32. End;
  33. Procedure Main; {求最长前缀的过程}
  34. Var
  35. I,J :Integer;
  36. Procedure See; {查看此位是否为前缀}
  37. Var
  38. I :Byte;
  39. X,Y :Integer;
  40. Begin
  41. Bo[J]:=False;
  42. For I:=1 To N Do
  43. Begin {考察每个基元}
  44. X:=J;Y:=Ji[I].Lst;
  45. While (Y>0) And (Ji[I].St[Y]=Ch[X]) Do
  46. Begin
  47. Dec(X);
  48. Dec(Y);
  49. If X<0 Then X:=21;
  50. End;
  51. If (Y=0) And (Bo[X]) Then
  52. Begin
  53. Bo[J]:=True;
  54. Exit;
  55. End;
  56. End;
  57. End;
  58. Begin
  59. Assign(F,Datafile);
  60. Reset(F);
  61. Big:=0; {边读入边判定}
  62. Tot:=0;
  63. Bo[0]:=True;
  64. J:=0;
  65. While (Tot-Big<20) And (Ch[J]<>'.') Do {如果超过20位不连续或读完文件,结束}
  66. Begin
  67. Inc(Tot);Inc(J);
  68. If J>21 Then J:=0;
  69. Readln(F,Ch[J]);
  70. If Ch[J]<>'.' Then
  71. Begin
  72. See;
  73. If Bo[J] Then Big:=Tot;
  74. End;
  75. End;
  76. Close(F);
  77. End;
  78. Procedure Print; {输出数据}
  79. Begin
  80. Assign(F,Outputfile);
  81. Rewrite(F);
  82. Writeln(F,Big);
  83. Close(F);
  84. End;
  85. Begin
  86. Init; {输入}
  87. Main; {动态规划求最长前缀}
  88. Print; {输出}
  89. End.