fork download
copy 
  1. program casino; (*con Algoritmo di Booth*)
  2. Uses sysutils;
  3. {$H+}
  4. const lung=1000000;
  5. var  N,M,C,w,v,coppie,index:Int64;
  6.      S,S_ruotate:array[0..lung] of AnsiString;
  7.      funz_errore : array[0..2000000] of Int64;
  8.      accoppiamenti:array[0..lung] of int64;
  9.      accoppiata: array[0..lung] of boolean;
  10.  
  11. function LexicalMinRotation(var x: AnsiString):Int64;
  12. var 
  13. len,K,i,j:Int64;
  14.  
  15. begin
  16.    x:=x+x; (*concatenare la stringa con se stessa*)
  17.    len:=length(x); 
  18.    for i:=0 to len do funz_errore[i]:=-1; (*inizializzare il vettore, di dimensione doppia della lunghezza della stringa,chiamato funzione_errore a -1*)
  19.    K:=1; (*indice che corrisponde al candidato corrente alla rotazione più piccola. Ricordare che le Ansistring iniziano da 1*)
  20.    for j:=2 to len do   (*confronta il carattere in j con il carattere in K+funz_errore[k]*)
  21.            begin
  22.              i:= funz_errore[j-k-1];
  23.              while (i <> -1 ) and (x[j] <> x[(k + i+1 )]) do   (*Se c'è una discrepanza aggiorna il valore di k*)
  24.                             begin
  25.                               if x[j] < x[(k + i+1 )] then k:= j - i - 1;
  26.                               i:=funz_errore[i];               (*modificare la funzione errore in base al confronto effettuato *)
  27.                             end;                           
  28.             if (i = -1) and (x[j] <> x[(k + i+1 )]) then
  29.                                                        begin
  30.                                                           if x[j] < x[(k + i+1 )] then k:= j;
  31.                                                           funz_errore[j - k]:= -1;
  32.                                                        end           
  33.                                                     else   funz_errore[j - k]:= i + 1;
  34.  
  35.          end;   
  36.  LexicalMinRotation:=k; (*dopo aver completato il processo k indica indice della rotazione minima*)
  37.  
  38. end;
  39.  
  40. begin
  41.    (*assign(input, 'input.txt'); reset(input);
  42.    assign(output, 'output.txt'); rewrite(output);*)
  43.    readln (N,M);
  44.    for w:=0 to N-1 do begin readln(S[w]);  S[w]:=Trim(S[w]); accoppiamenti[w]:=0; accoppiata[w]:=false; end;
  45.    coppie:=0;  
  46.   for w:=0 to N-1 do
  47.           begin
  48.             index:=LexicalMinRotation(S[w]);
  49.             S_ruotate[w]:=copy(S[w],index,M);
  50.           end;
  51.    for w:=0 to N-2 do  
  52.                begin 
  53.                   if accoppiata[w]= false then
  54.                     for v:=w+1 to N-1 do
  55.                        begin
  56.                           if accoppiata[v]=false then
  57.                                               begin
  58.                                                    C:= CompareStr(S_ruotate[w], S_ruotate[v]);
  59.                                                    if C=0 then begin  accoppiamenti[w]:=accoppiamenti[w]+1; accoppiata[w]:=true; accoppiata[v]:=true; end;
  60.                                                end
  61.                                         else continue;
  62.                         end;
  63.                end;         
  64.     for w:=0 to N-1 do 
  65.                begin
  66.                  if accoppiamenti[w]=1 then coppie:=coppie+1
  67.                                        else if accoppiamenti[w]>1 then coppie:=coppie+((accoppiamenti[w]+1)*(accoppiamenti[w]) div 2);
  68.                end;
  69.     writeln (coppie);
  70. end.
Success #stdin #stdout 0.02s 5284KB
comments (?)
stdin
copy 
3 6
adaada
aaadda
aadaad
stdout
copy 
1
https://ideone.com/kZuICq
language:
Pascal (fpc 3.0.4)
created:
18 hours 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!