fork download 
  1. program casino;  
  2. Uses sysutils;
  3. {$H+}
  4. const lung=1000000;
  5. type elenco=array[0..lung-1] of Qword;
  6. var  N,M,w,v,C,t,coppie,index:Qword;
  7.      S,S_ruotate:array[0..lung] of AnsiString;
  8.      funz_errore: array[0..1000000] of Int64;
  9.      H, accoppiamenti:elenco;
  10.      accoppiata:array[0..1000000] of boolean;
  11.  
  12. function LexicalMinRotation(var x: AnsiString):Qword;
  13. var 
  14. len,K,j:Qword;
  15. i:Int64;
  16.  
  17. begin
  18.    x:=x+x; 
  19.    len:=length(x); 
  20.    for i:=0 to len do funz_errore[i]:=-1; 
  21.    K:=1; 
  22.    for j:=2 to len do   
  23.            begin
  24.              i:= funz_errore[j-k-1];
  25.              while (i <> -1 ) and (x[j] <> x[(k + i+1 )]) do   
  26.                             begin
  27.                               if x[j] < x[(k + i+1 )] then k:= j - i - 1;
  28.                               i:=funz_errore[i];               
  29.                             end;                           
  30.             if (i = -1) and (x[j] <> x[(k + i+1 )]) then
  31.                                                        begin
  32.                                                           if x[j] < x[(k + i+1 )] then k:= j;
  33.                                                           funz_errore[j - k]:= -1;
  34.                                                        end           
  35.                                                     else   funz_errore[j - k]:= i + 1;
  36.  
  37.          end;   
  38.  LexicalMinRotation:=k; 
  39.  
  40. end;
  41.  
  42. function Rabin (var x: Ansistring) :Qword;
  43. var len, i, R,base,d,q:Qword;
  44. begin
  45.    d:=1; R:=0; len:=length(x); base:=26; q:=8446744073709551615;
  46.    for i := 1  to len-1 do  d := (d * base) mod q ; 
  47.    for i := 1 to len do  R:= (base*R + (ord(x[i])) ) mod q;  
  48.    Rabin:= R; 
  49. end; 
  50.  
  51.  
  52.  
  53. begin
  54.    (*assign(input, 'input.txt'); reset(input);
  55.    assign(output, 'output.txt'); rewrite(output);*)
  56.    readln (N,M);
  57.    for w:=0 to N-1 do begin readln(S[w]);  S[w]:=Trim(S[w]); end;
  58.    for w:=0 to N-1 do begin H[w]:=0; accoppiata[w]:=false; accoppiamenti[w]:=0; end;
  59.    coppie:=0;  
  60.   for w:=0 to N-1 do
  61.           begin
  62.             index:=LexicalMinRotation(S[w]);
  63.             S_ruotate[w]:=copy(S[w],index,M);  
  64.             H[w]:=Rabin(S_ruotate[w]);
  65.           end;
  66.    w:=0;       
  67.    while w<N-1 do  
  68.        begin 
  69.            if accoppiata[w]=false then 
  70.                        begin
  71.                            for v:=w+1 to N-1 do
  72.                                begin
  73.                                       if H[w]=H[v] then  
  74.                                             begin                                    
  75.                                               C:= CompareStr(S_ruotate[w], S_ruotate[v]);
  76.                                               if C=0 then begin accoppiamenti[w]:=accoppiamenti[w]+1; accoppiata[w]:=true; accoppiata[v]:=true; end;
  77.                                             end;
  78.                               end; 
  79.                             w:=w+1;             
  80.                        end
  81.                    else begin w:=w+1;   continue; end; 
  82.        end;  
  83.    for w:=0 to N-1  do 
  84.                begin
  85.                   if accoppiamenti[w] =1 then coppie:=coppie+1
  86.                                           else if accoppiamenti[w]>1 then coppie:=coppie+((accoppiamenti[w]+1)*(accoppiamenti[w]) div 2);
  87.                end;         
  88.    writeln (coppie);
  89. end.
Success #stdin #stdout 0.02s 6716KB
comments (?)
stdin 
4 4
abcd
xbcd
cdab
dabc
stdout 
3
https://ideone.com/8EV500
language:
Pascal (fpc 3.0.4)
created:
273 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!