fork download
copy 
  1. using static IO;
  2. public class IO
  3. {
  4. public static IO Cin = new();
  5. public static StreamReader reader = new(Console.OpenStandardInput());
  6. public static StreamWriter writer = new(Console.OpenStandardOutput());
  7. public static implicit operator string(IO _) => reader.ReadLine();
  8. public static implicit operator char[](IO _) => reader.ReadLine().ToArray();
  9. public static implicit operator int(IO _) => int.Parse(reader.ReadLine());
  10. public static implicit operator double(IO _) => double.Parse(reader.ReadLine());
  11. public static implicit operator string[](IO _) => reader.ReadLine().Split();
  12. public static implicit operator int[](IO _) => Array.ConvertAll(reader.ReadLine().Split(), int.Parse);
  13. public void Deconstruct(out int a, out int b) { int[] r = Cin; (a, b) = (r[0], r[1]); }
  14. public void Deconstruct(out int a, out int b, out int c) { int[] r = Cin; (a, b, c) = (r[0], r[1], r[2]); }
  15. public static void Loop(int end, Action<int> action, int start = 0, in int add = 1) { for (; start < end; start += add) action(start); }
  16. public static object? Cout { set { writer.Write(value); } }
  17. public static object? Coutln { set { writer.WriteLine(value); } }
  18. public static void Main() { Program.Coding(); writer.Flush(); }
  19. }
  20. class Program
  21. {
  22.     public static void Coding()
  23.     {
  24.         checked
  25.         {
  26.             string text = Cin;
  27.             int n = text.Length;
  28.  
  29.             int[] suffix = Enumerable.Range(0, n).ToArray();
  30.             int[] rank = text.Select(x => x - 'a').ToArray();
  31.             int[] next = new int[n];
  32.  
  33.             for (int skip = 1; skip < n; skip <<= 1)
  34.             {
  35.                 int Compare(int a, int b)
  36.                 {
  37.                     if (rank[a] != rank[b]) return rank[a].CompareTo(rank[b]);
  38.                     int ra = (a + skip < n) ? rank[a + skip] : -1;
  39.                     int rb = (b + skip < n) ? rank[b + skip] : -1;
  40.                     return ra.CompareTo(rb);
  41.                 }
  42.                 Array.Sort(suffix, Compare);
  43.  
  44.                 next[suffix[0]] = 0;
  45.                 for (int i = 1; i < n; i++)
  46.                 {
  47.                     next[suffix[i]] = next[suffix[i - 1]] + (0 == Compare(suffix[i - 1], suffix[i]) ? 0 : 1);
  48.                 }
  49.                 Array.Copy(next, rank, n);
  50.  
  51.                 if (rank[suffix[n - 1]] + 1 >= n) break;
  52.             }
  53.  
  54.             int[] lcp = new int[n];
  55.             int h = 0;
  56.             for (int i = 0; i < n; i++)
  57.             {
  58.                 if (rank[i] + 1 >= n)
  59.                 {
  60.                     h = 0;
  61.                     continue;
  62.                 }
  63.  
  64.                 for (int j = suffix[rank[i] + 1]; i + h < n && j + h < n && text[i + h] == text[j + h];) h++;
  65.                 lcp[rank[i]] = h;
  66.  
  67.                 if (h > 0) h--;
  68.             }
  69.  
  70.             Coutln = string.Join(' ', suffix.Select(i => i + 1));
  71.             Cout = "x " + string.Join(' ', lcp.SkipLast(1));
  72.         }
  73.     }
  74. }
Success #stdin #stdout 0.09s 28440KB
comments (?)
stdin
copy 
abracadabra
stdout
copy 
11 8 1 4 6 9 2 5 7 10 3
x 1 4 1 1 0 3 0 0 0 2
https://ideone.com/YdfFK1
11 8 1 4 6 9 2 5 7 10 3
x 1 4 1 1 0 3 0 0 0 2
language:
C# (NET 6.0)
created:
17 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!