From http://community.9cbs.net/expert/topicview1.asp?id=3660145quickKeyboard () This is a basic issue in NOI teaching. When you want to see if an element is in a collection, use the HASH hash table The highest efficiency. I have been written, complexity: 5000 5000. Delphi5 pass: Program ab5000; {$ appty console}
Const maxval = 30000;
VAR A, B: Array [0..5000] of integer; D: array [0..maxval-1] of byte; i: integer;
BEGIN / / Fill in random data in arguments A, B. Randomize; for i: = 0 to 5000 do begin a [i]: = random (maxval); b [i]: = random (maxval);
/ / Empty Hash Table Fillchar (D, 30000 * SizeOf (Byte), 0); // Constructs an Hash Table for i: = 0 to 5000 DO INC (D [A [i] mod maxval]); //// Find an element for i: = 0 to 5000 do if d [b [i] mod maxval] <> 0 THEN WRITELN; Readln; End If it is a string array, then change the Hash function. The Hash function I used above is "surplus", for the string, can consider using the execution connection format (ELF) Hash function, the code is as follows: Function Elfhash (var s: string): Integer; Var g, h, i: longword Begin H: = 0; for i: = 1 to Length (s) do begin h: = h SHL 4 ORD (S [i]); g: = h and $ f0000000; if g <> 0 THEN H: = h xor (g shr 24); h: = h and (not g); end; ELFHASH: = H mod m; end; This hash function earliest uses file system for UNIX system, which is very effective for long short-, The probability of conflict is very small for different s. Where m is the size of the Hash table.
