HackerRank - world code sprint #5 - build a palindrome - study C# code

buildaPalindrome1.cs

using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading;

public class Solver
{
    int[] BuildSuffixArray(string s)
    {
        int n = s.Length;
        var cnt = new int[128];
        for (int i = 0; i < n; ++i)
            ++cnt[s[i]];
        for (int i = 1; i < 128; ++i)
            cnt[i] += cnt[i - 1];

        var p = new int[n];
        for (int i = 0; i < n; ++i)
            p[--cnt[s[i]]] = i;

        var c = new int[n];
        int classes = 1;
        for (int i = 1; i < n; ++i)
        {
            if (s[p[i]] != s[p[i - 1]])
                ++classes;
            c[p[i]] = classes - 1;
        }

        var pn = new int[n];
        for (int h = 0; 1 << h < n; ++h)
        {
            var cn = new int[n];
            for (int i = 0; i < n; ++i)
            {
                pn[i] = p[i] - (1 << h);
                if (pn[i] < 0)
                    pn[i] += n;
            }
            cnt = new int[classes];
            for (int i = 0; i < n; ++i)
                ++cnt[c[pn[i]]];
            for (int i = 1; i < classes; ++i)
                cnt[i] += cnt[i - 1];
            for (int i = n - 1; i >= 0; --i)
                p[--cnt[c[pn[i]]]] = pn[i];
            cn[p[0]] = 0;
            classes = 1;
            for (int i = 1; i < n; ++i)
            {
                int mid1 = (p[i] + (1 << h)) % n;
                int mid2 = (p[i - 1] + (1 << h)) % n;
                if (c[p[i]] != c[p[i - 1]] || c[mid1] != c[mid2])
                    ++classes;
                cn[p[i]] = classes - 1;
            }
            c = cn;
        }

        return p;
    }

    int[] BuildLcp(string s, int[] p)
    {
        int n = s.Length;

        var rank = new int[n];
        for (int i = 0; i < n; ++i)
            rank[p[i]] = i;

        var lcp = new int[n];
        for (int i = 0, k = 0; i < n; ++i)
        {
            if (k > 0)
                k--;
            if (rank[i] == n - 1)
            {
                lcp[n - 1] = -1;
                k = 0;
                continue;
            }
            int j = p[rank[i] + 1];
            while (Math.Max(i + k, j + k) < n && s[i + k] == s[j + k])
                k++;
            lcp[rank[i]] = k;
        }

        return lcp;
    }

    public void Solve()
    {
        for (int tt = ReadInt(); tt > 0; tt--)
        {
            string s = ReadToken();
            string t = ReadToken();

            int n = s.Length;
            int m = t.Length;
            var scnt = new int[26];
            var tcnt = new int[26];
            var spos = new int[26];
            var tpos = new int[26];
            for (int i = 0; i < n; i++)
            {
                scnt[s[i] - 'a']++;
                spos[s[i] - 'a'] = i;
            }
            for (int i = 0; i < m; i++)
            {
                tcnt[t[i] - 'a']++;
                tpos[t[i] - 'a'] = i;
            }
            bool ok = false;
            for (int i = 0; i < 26; i++)
                if (scnt[i] > 0 && tcnt[i] > 0)
                    ok = true;
            if (!ok)
            {
                Write(-1);
                continue;
            }
            
            string rs = new string(s.Reverse().ToArray());
            string st = rs + t + "#";
            var sa = BuildSuffixArray(st);
            var rsa = new int[n + m];
            for (int i = 0; i < n + m; i++)
                rsa[sa[i + 1]] = i + 1;
            var lcp = BuildLcp(st, sa);
            
            var dp = new int[n + m + 1];
            var dpx = new int[n + m + 1];
            int p = n + m - 1;
            while (sa[p] >= n == sa[p + 1] >= n)
                p--;
            int v = lcp[p], z = p + 1;
            while (p > 0)
            {
                if (sa[p] >= n != sa[p + 1] >= n)
                {
                    v = lcp[p];
                    z = p + 1;
                    if (v > dp[z])
                    {
                        dp[z] = v;
                        dpx[z] = sa[p];
                    }
                }
                v = Math.Min(v, lcp[p]);
                dp[p] = v;
                dpx[p] = sa[z];
                p--;
            }

            var spo = new int[n];
            int l = 0, r = -1;
            for (int i = 0; i < n; ++i)
            {
                int k = i > r ? 1 : Math.Min(spo[l + r - i], r - i);
                while (i + k < n && i - k >= 0 && s[i + k] == s[i - k])
                    ++k;
                spo[i] = k;
                if (i + k > r)
                {
                    l = i - k + 1;
                    r = i + k - 1;
                }
            }

            var spe = new int[n];
            l = 0;
            r = -1;
            for (int i = 0; i < n; i++)
            {
                int k = i > r ? 0 : Math.Min(spe[l + r - i + 1], r - i + 1);

                while (i + k < n && i - k - 1 >= 0 && s[i + k] == s[i - k - 1]) k++;
                spe[i] = k;

                if (i + k - 1 > r)
                {
                    l = i - k;
                    r = i + k - 1;
                }
            }

            var tpo = new int[m];
            l = 0;
            r = -1;
            for (int i = 0; i < m; ++i)
            {
                int k = i > r ? 1 : Math.Min(tpo[l + r - i], r - i);
                while (i + k < m && i - k >= 0 && t[i + k] == t[i - k])
                    ++k;
                tpo[i] = k;
                if (i + k > r)
                {
                    l = i - k + 1;
                    r = i + k - 1;
                }
            }

            var tpe = new int[m];
            l = 0;
            r = -1;
            for (int i = 0; i < m; i++)
            {
                int k = i > r ? 0 : Math.Min(tpe[l + r - i + 1], r - i + 1);

                while (i + k < m && i - k - 1 >= 0 && t[i + k] == t[i - k - 1]) k++;
                tpe[i] = k;

                if (i + k - 1 > r)
                {
                    l = i - k;
                    r = i + k - 1;
                }
            }

            int best = 0;
            var o = new List<Tuple<int, int, int, int>>();
            for (int i = 0; i < n; i++)
            {
                p = i - spo[i];
                int len = spo[i] * 2 - 1;
                int sym = 0;
                if (p >= 0)
                    sym = dp[rsa[n - p - 1]];
                if (sym > 0 && len + 2 * sym > best)
                {
                    best = len + 2 * sym;
                    o.Clear();
                    o.Add(Tuple.Create(p - sym + 1, p + len, dpx[rsa[n - p - 1]] - n, dpx[rsa[n - p - 1]] - n + sym - 1));
                }
                else if (sym > 0 && len + 2 * sym == best)
                    o.Add(Tuple.Create(p - sym + 1, p + len, dpx[rsa[n - p - 1]] - n, dpx[rsa[n - p - 1]] - n + sym - 1));

                p = spe[i] > 0 ? i - spe[i] - 1 : i;
                len = spe[i] * 2;
                sym = 0;
                if (p >= 0)
                    sym = dp[rsa[n - p - 1]];
                if (sym > 0 && len + 2 * sym > best)
                {
                    best = len + 2 * sym;
                    o.Clear();
                    o.Add(Tuple.Create(p - sym + 1, p + len, dpx[rsa[n - p - 1]] - n, dpx[rsa[n - p - 1]] - n + sym - 1));
                }
                else if (sym > 0 && len + 2 * sym == best)
                    o.Add(Tuple.Create(p - sym + 1, p + len, dpx[rsa[n - p - 1]] - n, dpx[rsa[n - p - 1]] - n + sym - 1));
            }

            for (int i = 0; i < m; i++)
            {
                p = i + tpo[i];
                int len = tpo[i] * 2 - 1;
                int sym = 0;
                if (p < m)
                    sym = dp[rsa[n + p]];
                if (sym > 0 && len + 2 * sym > best)
                {
                    best = len + 2 * sym;
                    o.Clear();
                    o.Add(Tuple.Create(n - dpx[rsa[n + p]] - sym, n - dpx[rsa[n + p]] - 1, i - tpo[i] + 1, p + sym - 1));
                }
                else if (sym > 0 && len + 2 * sym == best)
                    o.Add(Tuple.Create(n - dpx[rsa[n + p]] - sym, n - dpx[rsa[n + p]] - 1, i - tpo[i] + 1, p + sym - 1));

                p = tpe[i] > 0 ? i + tpe[i] : i;
                len = tpe[i] * 2;
                sym = 0;
                if (p < m)
                    sym = dp[rsa[n + p]];
                if (sym > 0 && len + 2 * sym > best)
                {
                    best = len + 2 * sym;
                    o.Clear();
                    o.Add(Tuple.Create(n - dpx[rsa[n + p]] - sym, n - dpx[rsa[n + p]] - 1, i - tpe[i], p + sym - 1));
                }
                else if (sym > 0 && len + 2 * sym == best)
                    o.Add(Tuple.Create(n - dpx[rsa[n + p]] - sym, n - dpx[rsa[n + p]] - 1, i - tpe[i], p + sym - 1));
            }

            //for (int i = 0; i < n; i++)
            //{
            //    if (spo[i] * 2 - 1 > best)
            //    {
            //        for (int j = 0; j + 1 < spo[i]; j++)
            //        {
            //            int len = spo[i] * 2 - 1 - 2 * j;
            //            if (len < best)
            //                break;
            //            int ch = s[i - spo[i] + 1 + j] - 'a';
            //            if (tcnt[ch] > 0)
            //            {
            //                if (len > best)
            //                {
            //                    best = len;
            //                    o.Clear();
            //                    o.Add(Tuple.Create(i - spo[i] + 1 + j, i - spo[i] + 1 + j + len - 2, tpos[ch], tpos[ch]));
            //                }
            //                else if (len == best)
            //                    o.Add(Tuple.Create(i - spo[i] + 1 + j, i - spo[i] + 1 + j + len - 2, tpos[ch], tpos[ch]));
            //            }
            //        }
            //    }
            //}

            string ans = "";
            foreach (var op in o)
            {
                string w = s.Substring(op.Item1, op.Item2 - op.Item1 + 1) + t.Substring(op.Item3, op.Item4 - op.Item3 + 1);
                if (ans == "" || string.Compare(w, ans) < 0)
                    ans = w;
            }
            //Write(best, sbestl, sbestr, tbestl, tbestr);
            Write(ans);
        }
    }

    #region Main

    protected static TextReader reader;
    protected static TextWriter writer;
    static void Main()
    {
#if DEBUG
        reader = new StreamReader("..\\..\\input.txt");
        //reader = new StreamReader(Console.OpenStandardInput());
        writer = Console.Out;
        //writer = new StreamWriter("..\\..\\output.txt");
#else
        reader = new StreamReader(Console.OpenStandardInput());
        writer = new StreamWriter(Console.OpenStandardOutput());
        //reader = new StreamReader("input.txt");
        //writer = new StreamWriter("output.txt");
#endif
        try
        {
            new Solver().Solve();
            //var thread = new Thread(new Solver().Solve, 1024 * 1024 * 128);
            //thread.Start();
            //thread.Join();
        }
        catch (Exception ex)
        {
#if DEBUG
            Console.WriteLine(ex);
#else
            throw;
#endif
        }
        reader.Close();
        writer.Close();
    }

    #endregion

    #region Read / Write
    private static Queue<string> currentLineTokens = new Queue<string>();
    private static string[] ReadAndSplitLine() { return reader.ReadLine().Split(new[] { ' ', '\t', }, StringSplitOptions.RemoveEmptyEntries); }
    public static string ReadToken() { while (currentLineTokens.Count == 0)currentLineTokens = new Queue<string>(ReadAndSplitLine()); return currentLineTokens.Dequeue(); }
    public static int ReadInt() { return int.Parse(ReadToken()); }
    public static long ReadLong() { return long.Parse(ReadToken()); }
    public static double ReadDouble() { return double.Parse(ReadToken(), CultureInfo.InvariantCulture); }
    public static int[] ReadIntArray() { return ReadAndSplitLine().Select(int.Parse).ToArray(); }
    public static long[] ReadLongArray() { return ReadAndSplitLine().Select(long.Parse).ToArray(); }
    public static double[] ReadDoubleArray() { return ReadAndSplitLine().Select(s => double.Parse(s, CultureInfo.InvariantCulture)).ToArray(); }
    public static int[][] ReadIntMatrix(int numberOfRows) { int[][] matrix = new int[numberOfRows][]; for (int i = 0; i < numberOfRows; i++)matrix[i] = ReadIntArray(); return matrix; }
    public static int[][] ReadAndTransposeIntMatrix(int numberOfRows)
    {
        int[][] matrix = ReadIntMatrix(numberOfRows); int[][] ret = new int[matrix[0].Length][];
        for (int i = 0; i < ret.Length; i++) { ret[i] = new int[numberOfRows]; for (int j = 0; j < numberOfRows; j++)ret[i][j] = matrix[j][i]; } return ret;
    }
    public static string[] ReadLines(int quantity) { string[] lines = new string[quantity]; for (int i = 0; i < quantity; i++)lines[i] = reader.ReadLine().Trim(); return lines; }
    public static void WriteArray<T>(IEnumerable<T> array) { writer.WriteLine(string.Join(" ", array)); }
    public static void Write(params object[] array) { WriteArray(array); }
    public static void WriteLines<T>(IEnumerable<T> array) { foreach (var a in array)writer.WriteLine(a); }
    private class SDictionary<TKey, TValue> : Dictionary<TKey, TValue>
    {
        public new TValue this[TKey key]
        {
            get { return ContainsKey(key) ? base[key] : default(TValue); }
            set { base[key] = value; }
        }
    }
    private static T[] Init<T>(int size) where T : new() { var ret = new T[size]; for (int i = 0; i < size; i++)ret[i] = new T(); return ret; }
    #endregion
}