fork download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4.  
  5.  
  6. public class Main {
  7. 	/*
  8.      * Create the LCP array from the suffix array
  9.      * @param s the input array populated from 0..N-1, with available pos N
  10.      * @param sa the already-computed suffix array 0..N-1
  11.      * @param LCP the resulting LCP array 0..N-1
  12.      */
  13.     public static void makeLCPArray( int [ ] s, int [ ] sa, int [ ] LCP )
  14.     {
  15.         int N = sa.length;
  16.         int [ ] rank = new int[ N ];
  17.  
  18.         s[ N ] = -1;
  19.         for( int i = 0; i < N; i++ )
  20.             rank[ sa[ i ] ] = i;
  21.  
  22.         int h = 0;
  23.         for( int i = 0; i < N; i++ )
  24.             if( rank[ i ] > 0 )
  25.             {
  26.                 int j = sa[ rank[ i ] - 1 ];
  27.  
  28.                 while( s[ i + h ] == s[ j + h ] )
  29.                     h++;
  30.  
  31.                 LCP[ rank[ i ] ] = h;
  32.                 if( h > 0 )
  33.                     h--;
  34.             }
  35.     }
  36.  
  37.     /*
  38.      * Fill in the suffix array information for String str
  39.      * @param str the input String
  40.      * @param sa existing array to place the suffix array
  41.      */
  42.     public static void createSuffixArray( String str, int [ ] sa, int [ ] LCP )
  43.     {        
  44.         int N = str.length( );
  45.  
  46.         int [ ] s = new int[ N + 3 ];
  47.         int [ ] SA = new int[ N + 3 ];
  48.  
  49.         for( int i = 0; i < N; i++ )
  50.             s[ i ] = str.charAt( i );
  51.  
  52.         makeSuffixArray( s, SA, N, 256 );
  53.  
  54.         for( int i = 0; i < N; i++ )
  55.             sa[ i ] = SA[ i ];
  56.  
  57.         makeLCPArray( s, sa, LCP );
  58.     }
  59.  
  60.  
  61.     // find the suffix array SA of s[0..n-1] in {1..K}^n
  62.     // require s[n]=s[n+1]=s[n+2]=0, n>=2
  63.     public static void makeSuffixArray( int [ ] s, int [ ] SA, int n, int K )
  64.     {
  65.         int n0 = ( n + 2 ) / 3;
  66.         int n1 = ( n + 1 ) / 3;
  67.         int n2 = n / 3;
  68.         int t = n0 - n1;  // 1 iff n%3 == 1
  69.         int n12 = n1 + n2 + t;
  70.  
  71.         int [ ] s12  = new int[ n12 + 3 ];
  72.         int [ ] SA12 = new int[ n12 + 3 ];
  73.         int [ ] s0   = new int[ n0 ];
  74.         int [ ] SA0  = new int[ n0 ];
  75.  
  76.         // generate positions in s for items in s12
  77.         // the "+t" adds a dummy mod 1 suffix if n%3 == 1
  78.         // at that point, the size of s12 is n12
  79.         for( int i = 0, j = 0; i < n + t; i++ )
  80.             if( i % 3 != 0 )
  81.                 s12[ j++ ] = i;
  82.  
  83.         int K12 = assignNames( s, s12, SA12, n0, n12, K );
  84.  
  85.         computeS12( s12, SA12, n12, K12 );
  86.         computeS0( s, s0, SA0, SA12, n0, n12, K );
  87.         merge( s, s12, SA, SA0, SA12, n, n0, n12, t );
  88.     }
  89.  
  90.     // Assigns the new supercharacter names.
  91.     // At end of routine, SA will have indices into s, in sorted order
  92.     // and s12 will have new character names
  93.     // Returns the number of names assigned; note that if
  94.     // this value is the same as n12, then SA is a suffix array for s12.
  95.     private static int assignNames( int [ ] s, int [ ] s12, int [ ] SA12,
  96.                                    int n0, int n12, int K )
  97.     {
  98.            // radix sort the new character trios
  99.         radixPass( s12 , SA12, s, 2, n12, K );
  100.         radixPass( SA12, s12 , s, 1, n12, K );  
  101.         radixPass( s12 , SA12, s, 0, n12, K );
  102.  
  103.           // find lexicographic names of triples
  104.         int name = 0;
  105.         int c0 = -1, c1 = -1, c2 = -1;
  106.  
  107.         for( int i = 0; i < n12; i++ )
  108.         {
  109.             if( s[ SA12[ i ] ] != c0 || s[ SA12[ i ] + 1 ] != c1
  110.                                      || s[ SA12[ i ] + 2 ] != c2 )
  111.             { 
  112.                 name++;
  113.                 c0 = s[ SA12[ i ] ];
  114.                 c1 = s[ SA12[ i ] + 1 ];
  115.                 c2 = s[ SA12[ i ] + 2 ];
  116.             }
  117.  
  118.             if( SA12[ i ] % 3 == 1 )
  119.                 s12[ SA12[ i ] / 3 ]      = name;
  120.             else
  121.                 s12[ SA12[ i ] / 3 + n0 ] = name; 
  122.        }
  123.  
  124.        return name;
  125.     }
  126.  
  127.  
  128.     // stably sort in[0..n-1] with indices into s that has keys in 0..K
  129.     // into out[0..n-1]; sort is relative to offset into s
  130.     // uses counting radix sort
  131.     private static void radixPass( int [ ] in, int [ ] out, int [ ] s, int offset,
  132.                                   int n, int K ) 
  133.     { 
  134.         int [ ] count = new int[ K + 2 ];            // counter array
  135.  
  136.         for( int i = 0; i < n; i++ )
  137.             count[ s[ in[ i ] + offset ] + 1 ]++;    // count occurences
  138.  
  139.         for( int i = 1; i <= K + 1; i++ )            // compute exclusive sums
  140.             count[ i ] += count[ i - 1 ];
  141.  
  142.         for( int i = 0; i < n; i++ )
  143.             out[ count[ s[ in[ i ] + offset ] ]++ ] = in[ i ];      // sort
  144.     } 
  145.  
  146.     // stably sort in[0..n-1] with indices into s that has keys in 0..K
  147.     // into out[0..n-1]
  148.     // uses counting radix sort
  149.     private static void radixPass( int [ ] in, int [ ] out, int [ ] s, int n, int K ) 
  150.     { 
  151.         radixPass( in, out, s, 0, n, K );
  152.     }
  153.  
  154.  
  155.     // Compute the suffix array for s12, placing result into SA12
  156.     private static void computeS12( int [ ] s12, int [ ] SA12, int n12, int K12 )
  157.     {
  158.         if( K12 == n12 ) // if unique names, don't need recursion
  159.             for( int i = 0; i < n12; i++ )
  160.                 SA12[ s12[i] - 1 ] = i; 
  161.         else
  162.         {
  163.             makeSuffixArray( s12, SA12, n12, K12 );
  164.             // store unique names in s12 using the suffix array 
  165.             for( int i = 0; i < n12; i++ )
  166.                 s12[ SA12[ i ] ] = i + 1;
  167.         }
  168.     }
  169.  
  170.     private static void computeS0( int [ ] s, int [ ] s0, int [ ] SA0, int [ ] SA12,
  171.                                int n0, int n12, int K )
  172.     {
  173.         for( int i = 0, j = 0; i < n12; i++ )
  174.             if( SA12[ i ] < n0 )
  175.                 s0[ j++ ] = 3 * SA12[ i ];
  176.  
  177.         radixPass( s0, SA0, s, n0, K );
  178.     }
  179.  
  180.  
  181.     // merge sorted SA0 suffixes and sorted SA12 suffixes
  182.     private static void merge( int [ ] s, int [ ] s12,
  183.                               int [ ] SA, int [ ] SA0, int [ ] SA12,
  184.                               int n, int n0, int n12, int t )
  185.     {      
  186.         int p = 0, k = 0;
  187.  
  188.         while( t != n12 && p != n0 )
  189.         {
  190.             int i = getIndexIntoS( SA12, t, n0 ); // S12
  191.             int j = SA0[ p ];                     // S0
  192.  
  193.             if( suffix12IsSmaller( s, s12, SA12, n0, i, j, t ) )
  194.             { 
  195.                 SA[ k++ ] = i;
  196.                 t++;
  197.             }
  198.             else
  199.             { 
  200.                 SA[ k++ ] = j;
  201.                 p++;
  202.             }  
  203.         } 
  204.  
  205.         while( p < n0 )
  206.             SA[ k++ ] = SA0[ p++ ];
  207.         while( t < n12 )
  208.             SA[ k++ ] = getIndexIntoS( SA12, t++, n0 ); 
  209.     }
  210.  
  211.     private static int getIndexIntoS( int [ ] SA12, int t, int n0 )
  212.     {
  213.         if( SA12[ t ] < n0 )
  214.             return SA12[ t ] * 3 + 1;
  215.         else
  216.             return ( SA12[ t ] - n0 ) * 3 + 2;
  217.     }
  218.  
  219.     private static boolean leq( int a1, int a2, int b1, int b2 )
  220.       { return a1 < b1 || a1 == b1 && a2 <= b2; }
  221.  
  222.     private static boolean leq( int a1, int a2, int a3, int b1, int b2, int b3 )
  223.       { return a1 < b1 || a1 == b1 && leq( a2, a3,b2, b3 ); }
  224.  
  225.     private static boolean suffix12IsSmaller( int [ ] s, int [ ] s12, int [ ] SA12,
  226.                                              int n0, int i, int j, int t )
  227.     {
  228.         if( SA12[ t ] < n0 )  // s1 vs s0; can break tie after 1 character
  229.             return leq( s[ i ], s12[ SA12[ t ] + n0 ],
  230.                         s[ j ], s12[ j / 3 ] );
  231.         else                  // s2 vs s0; can break tie after 2 characters
  232.             return leq( s[ i ], s[ i + 1 ], s12[ SA12[ t ] - n0 + 1 ],
  233.                         s[ j ], s[ j + 1 ], s12[ j / 3 + n0 ] );
  234.     }
  235.  
  236.     public static void printV( int [ ]  a, String comment )
  237.     {
  238.         System.out.print( comment + ":" );
  239.         for( int x : a ) 
  240.             System.out.print( x + " " );
  241.  
  242.         System.out.println( );
  243.     }
  244.  
  245.     public static boolean isPermutation( int [ ] SA, int n )
  246.     {
  247.         boolean [ ] seen = new boolean [ n ];
  248.  
  249.         for( int i = 0; i < n; i++ )
  250.             seen[ i ] = false;
  251.  
  252.         for( int i = 0; i < n; i++ )
  253.             seen[ SA[ i ] ] = true;
  254.  
  255.         for( int i = 0; i < n; i++ )
  256.             if( !seen[ i ] )
  257.                 return false;
  258.  
  259.         return true;
  260.     }
  261.  
  262.     public static boolean sleq( int  [ ] s1, int start1, int [ ] s2, int start2 )
  263.     {
  264.         for( int i = start1, j = start2; ; i++, j++ )
  265.         {
  266.             if( s1[ i ] < s2[ j ] )
  267.                 return true;
  268.  
  269.             if( s1[ i ] > s2[ j ] )
  270.                 return false;
  271.         }
  272.     } 
  273.  
  274.     // Check if SA is a sorted suffix array for s
  275.     public static boolean isSorted( int [ ] SA, int [ ] s, int n )
  276.     {
  277.         for( int i = 0; i < n-1; i++ )
  278.             if( !sleq( s, SA[ i ], s, SA[ i + 1 ] ) )
  279.                 return false;
  280.  
  281.         return true;  
  282.     }
  283.  
  284.     public static void main(String[] args) throws NumberFormatException, IOException {
  285.     	BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
  286. 		 int t = Integer.parseInt(bf.readLine());
  287. 		 while(t-->0){
  288. 			 String s = bf.readLine();
  289. 			 int n = s.length();
  290. 			 int[] SA = new int[n];
  291. 			 int[] LCP = new int[n];
  292. 			 createSuffixArray( s, SA, LCP );
  293.  
  294. 			 int count = n - SA[0];
  295.  
  296. 			 for(int i = 1;i<n;i++)
  297. 			    	count += (n - SA[i]) - LCP[i];
  298.  
  299. 			 System.out.println(count);
  300. 		 }
  301. 	}
  302. }
Runtime error #stdin #stdout #stderr 0.07s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.lang.NumberFormatException: null
	at java.lang.Integer.parseInt(Integer.java:454)
	at java.lang.Integer.parseInt(Integer.java:527)
	at Main.main(Main.java:286)
https://ideone.com/kW5UFT
language:
Java (12.0.1)
created:
9 years 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!