Test results - Codility

Tasks Details

hard

1. FindThree

Find the longest border of a given string, that has three non-overlapping occurrences.

100%

Not assessed

A prefix of a string S is any leading contiguous part of S. A suffix of the string S is any trailing contiguous part of S. For example, "c" and "cod" are prefixes, and "ty" and "ity" are suffixes of the string "codility". For simplicity, we require prefixes and suffixes to be non-empty and shorter than the whole string S.

A border of a string S is any string that is both a prefix and a suffix. For example, "cut" is a border of a string "cutletcut", and a string "barbararhubarb" has two borders: "b" and "barb".

We are looking for such borders of S that have at least three non-overlapping occurrences; that is, for some string that occurs as a prefix, as a suffix and elsewhere in between. For example, for S = "barbararhubarb", the only such string is "b".

In this problem we consider only strings that consist of lower-case English letters (a−z).

Write a function:

class Solution { public int solution(string S); }

that, given a string S consisting of N characters, returns the length of its longest border that has at least three non-overlapping occurrences in the given string. If there is no such border in S, the function should return 0.

For example, given a string S as follows:

if S = "barbararhubarb" the function should return 1, as explained above;

if S = "ababab" the function should return 2, as "ab" and "abab" are both borders of S, but only "ab" has three non-overlapping occurrences;

if S = "baaab" the function should return 0, as its only border "b" occurs only twice.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..1,000,000];

string S is made only of lowercase letters (a−z).

Solution

Programming language used C#

Time spent on task 2 minutes

Notes

not defined yet

Code: 02:37:35 UTC, cs, verify, result: Passed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137

using System;
// you can also use other imports, for example:
// using System.Collections.Generic;
class Solution {
    public int solution(string S) {
        return Solve(S);
    }
    
    private class RabinKarp
    {
        public long B, M;
        public long[] RK, ER;
        public RabinKarp(long b, long m) { B = b; M = m; }
        public RabinKarp Initialize(int n, int ner) {
            RK = new long[n];
            ER = new long[ner]; ER[0] = 1;
            for (int i = 1; i < ner; ER[i] = (ER[i - 1] * B) % M, i++) ;
            return this;
        }
        public long this[int start, int end] {
            get { return (RK[end] - (RK[start-1] * ER[end - start + 1]) % M + M) % M; }
        }
        public static void BuildRKParams(string s, int start, int end, RabinKarp[] rks) {
            foreach (RabinKarp rk in rks)
                rk.RK[start] = s[start];
            for (int i = start+1; i <= end; i++)
                foreach (RabinKarp rk in rks)
                    rk.RK[i] = ((rk.RK[i - 1] * rk.B) % rk.M + s[i]) % rk.M;
        }
    }
    private class KMP
    {
        public int[] SkipSearchTable = null;
        public KMP(string pattern) {
            SkipSearchTable = BuildKMPSkipSearchTable(pattern, pattern.Length);
        }
        protected int[] BuildKMPSkipSearchTable(string ptn, int n)
        {
            int[] skipSearchTable = new int[n];
            int i = 2, j = 0;
            skipSearchTable[0] = -1; skipSearchTable[1] = 0;
            while (i < n) {
                if (ptn[i - 1] == ptn[j]) skipSearchTable[i++] = ++j;
                else if (j > 0) j = skipSearchTable[j];
                else skipSearchTable[i++] = 0;
            }
            return skipSearchTable;
        }
        public int Search(string s, int ell, int pLength, int start, int end)
        {
            int i = ell, j = start, k = start;
            end = end - pLength + 1;
            while (j <= end) {
                while (i < pLength && s[i] == s[i + j]) ++i;
                if (i >= pLength) {
                    while (k < ell && s[k] == s[j + k]) ++k;
                    if (k >= ell) return j;
                }
                j += (i - SkipSearchTable[i]);
                if (i == ell) k = k > 0 ? (k - 1) : 0;
                else
                    if (SkipSearchTable[i] <= ell) {
                        k = SkipSearchTable[i] >= 0 ? SkipSearchTable[i] : 0;
                        i = ell;
                    } else {
                        k = ell;
                        i = SkipSearchTable[i];
                    }
            }
            return -1;
        }
    }

    public int Solve(string S)
    {
        if (S.Length < 3) return 0;
        int n = S.Length, ell = 1, scanIdx = 0;
        for (; ell < n && S[ell - 1] == S[ell]; ell++) ;
        if (ell == n) return (n / 3);
        if (ell < n / 3) {
            KMP kmp = new KMP(S);
            scanIdx = (int)Math.Min(n / 3 - 1, kmp.SkipSearchTable[n - 1]);
            if (ell <= scanIdx)
            {
                RabinKarp[] rks = new RabinKarp[] {
                    new RabinKarp(29, 777333111).Initialize(n, scanIdx + 2),
                    new RabinKarp(31, 555111333).Initialize(n, scanIdx + 2)
                };
                RabinKarp.BuildRKParams(S, 0, scanIdx, rks);
                RabinKarp.BuildRKParams(S, n - scanIdx - 2, n-1, rks);
                for (int j = n - scanIdx - 1, idx = -1; scanIdx >= 0; scanIdx--, j++)
                {
                    if (ell > 1 && ell > scanIdx) break;
                    bool skip = false;
                    foreach (RabinKarp rk in rks) {
                        if (rk.RK[scanIdx] != rk[j, n - 1]) {
                            skip = true; break;
                        }
                    }
                    if (skip) continue;

                    idx = kmp.Search(S, (scanIdx == 0 && ell == 1) ? 0 : ell, scanIdx + 1, scanIdx + 1, n - scanIdx - 2);
                    if (idx < 0) continue;
                    if (idx == n) break;
                    if (idx >= 0) return scanIdx + 1;
                }
            }
        }
        if (scanIdx < 0) return 0;

        int ellRight = n, c0 = S[0];
        for (; ellRight > ell && S[ellRight - 1] == c0; ellRight--) ;
        if (n - ellRight <= 0) return 0;

        int min = (int)Math.Min(ell, n - ellRight);
        int ret = (int)Math.Min(min, ((int)Math.Max(ell, n - ellRight)) / 2);
        if (ret >= min) return min;
        scanIdx = ell; ell = -1;
        while (scanIdx < ellRight)
        {
            if (S[scanIdx] == c0) {
                if (ell < 0) ell = scanIdx;
                while (++scanIdx < ellRight && S[scanIdx] == c0) ;
                continue;
            }
            if (ell >= 0) {
                if (ret < scanIdx - ell) {
                    ret = scanIdx - ell;
                    if (ret >= min) return ret;
                }
                ell = -1;
            }
            scanIdx++;
        }
        return (int)Math.Min(min, ell < 0 ? ret : (int)Math.Max(ret, scanIdx - ell));
    }
}

Code: 02:38:25 UTC, cs, verify, result: Passed

using System;
// you can also use other imports, for example:
// using System.Collections.Generic;
class Solution {
    public int solution(string S) {
        return Solve(S);
    }
    
    private class RabinKarp
    {
        public long B, M;
        public long[] RK, ER;
        public RabinKarp(long b, long m) { B = b; M = m; }
        public RabinKarp Initialize(int n, int ner) {
            RK = new long[n];
            ER = new long[ner]; ER[0] = 1;
            for (int i = 1; i < ner; ER[i] = (ER[i - 1] * B) % M, i++) ;
            return this;
        }
        public long this[int start, int end] {
            get { return (RK[end] - (RK[start-1] * ER[end - start + 1]) % M + M) % M; }
        }
        public static void BuildRKParams(string s, int start, int end, RabinKarp[] rks) {
            foreach (RabinKarp rk in rks)
                rk.RK[start] = s[start];
            for (int i = start+1; i <= end; i++)
                foreach (RabinKarp rk in rks)
                    rk.RK[i] = ((rk.RK[i - 1] * rk.B) % rk.M + s[i]) % rk.M;
        }
    }
    private class KMP
    {
        public int[] SkipSearchTable = null;
        public KMP(string pattern) {
            SkipSearchTable = BuildKMPSkipSearchTable(pattern, pattern.Length);
        }
        protected int[] BuildKMPSkipSearchTable(string ptn, int n)
        {
            int[] skipSearchTable = new int[n];
            int i = 2, j = 0;
            skipSearchTable[0] = -1; skipSearchTable[1] = 0;
            while (i < n) {
                if (ptn[i - 1] == ptn[j]) skipSearchTable[i++] = ++j;
                else if (j > 0) j = skipSearchTable[j];
                else skipSearchTable[i++] = 0;
            }
            return skipSearchTable;
        }
        public int Search(string s, int ell, int pLength, int start, int end)
        {
            int i = ell, j = start, k = start;
            end = end - pLength + 1;
            while (j <= end) {
                while (i < pLength && s[i] == s[i + j]) ++i;
                if (i >= pLength) {
                    while (k < ell && s[k] == s[j + k]) ++k;
                    if (k >= ell) return j;
                }
                j += (i - SkipSearchTable[i]);
                if (i == ell) k = k > 0 ? (k - 1) : 0;
                else
                    if (SkipSearchTable[i] <= ell) {
                        k = SkipSearchTable[i] >= 0 ? SkipSearchTable[i] : 0;
                        i = ell;
                    } else {
                        k = ell;
                        i = SkipSearchTable[i];
                    }
            }
            return -1;
        }
    }

    public int Solve(string S)
    {
        if (S.Length < 3) return 0;
        int n = S.Length, ell = 1, scanIdx = 0;
        for (; ell < n && S[ell - 1] == S[ell]; ell++) ;
        if (ell == n) return (n / 3);
        if (ell < n / 3) {
            KMP kmp = new KMP(S);
            scanIdx = (int)Math.Min(n / 3 - 1, kmp.SkipSearchTable[n - 1]);
            if (ell <= scanIdx)
            {
                RabinKarp[] rks = new RabinKarp[] {
                    new RabinKarp(29, 777333111).Initialize(n, scanIdx + 2),
                    new RabinKarp(31, 555111333).Initialize(n, scanIdx + 2)
                };
                RabinKarp.BuildRKParams(S, 0, scanIdx, rks);
                RabinKarp.BuildRKParams(S, n - scanIdx - 2, n-1, rks);
                for (int j = n - scanIdx - 1, idx = -1; scanIdx >= 0; scanIdx--, j++)
                {
                    if (ell > 1 && ell > scanIdx) break;
                    bool skip = false;
                    foreach (RabinKarp rk in rks) {
                        if (rk.RK[scanIdx] != rk[j, n - 1]) {
                            skip = true; break;
                        }
                    }
                    if (skip) continue;

                    idx = kmp.Search(S, (scanIdx == 0 && ell == 1) ? 0 : ell, scanIdx + 1, scanIdx + 1, n - scanIdx - 2);
                    if (idx < 0) continue;
                    if (idx == n) break;
                    if (idx >= 0) return scanIdx + 1;
                }
            }
        }
        if (scanIdx < 0) return 0;

        int ellRight = n, c0 = S[0];
        for (; ellRight > ell && S[ellRight - 1] == c0; ellRight--) ;
        if (n - ellRight <= 0) return 0;

        int min = (int)Math.Min(ell, n - ellRight);
        int ret = (int)Math.Min(min, ((int)Math.Max(ell, n - ellRight)) / 2);
        if (ret >= min) return min;
        scanIdx = ell; ell = -1;
        while (scanIdx < ellRight)
        {
            if (S[scanIdx] == c0) {
                if (ell < 0) ell = scanIdx;
                while (++scanIdx < ellRight && S[scanIdx] == c0) ;
                continue;
            }
            if (ell >= 0) {
                if (ret < scanIdx - ell) {
                    ret = scanIdx - ell;
                    if (ret >= min) return ret;
                }
                ell = -1;
            }
            scanIdx++;
        }
        return (int)Math.Min(min, ell < 0 ? ret : (int)Math.Max(ret, scanIdx - ell));
    }
}

Code: 02:38:30 UTC, cs, final, score: 100

using System;
// you can also use other imports, for example:
// using System.Collections.Generic;
class Solution {
    public int solution(string S) {
        return Solve(S);
    }
    
    private class RabinKarp
    {
        public long B, M;
        public long[] RK, ER;
        public RabinKarp(long b, long m) { B = b; M = m; }
        public RabinKarp Initialize(int n, int ner) {
            RK = new long[n];
            ER = new long[ner]; ER[0] = 1;
            for (int i = 1; i < ner; ER[i] = (ER[i - 1] * B) % M, i++) ;
            return this;
        }
        public long this[int start, int end] {
            get { return (RK[end] - (RK[start-1] * ER[end - start + 1]) % M + M) % M; }
        }
        public static void BuildRKParams(string s, int start, int end, RabinKarp[] rks) {
            foreach (RabinKarp rk in rks)
                rk.RK[start] = s[start];
            for (int i = start+1; i <= end; i++)
                foreach (RabinKarp rk in rks)
                    rk.RK[i] = ((rk.RK[i - 1] * rk.B) % rk.M + s[i]) % rk.M;
        }
    }
    private class KMP
    {
        public int[] SkipSearchTable = null;
        public KMP(string pattern) {
            SkipSearchTable = BuildKMPSkipSearchTable(pattern, pattern.Length);
        }
        protected int[] BuildKMPSkipSearchTable(string ptn, int n)
        {
            int[] skipSearchTable = new int[n];
            int i = 2, j = 0;
            skipSearchTable[0] = -1; skipSearchTable[1] = 0;
            while (i < n) {
                if (ptn[i - 1] == ptn[j]) skipSearchTable[i++] = ++j;
                else if (j > 0) j = skipSearchTable[j];
                else skipSearchTable[i++] = 0;
            }
            return skipSearchTable;
        }
        public int Search(string s, int ell, int pLength, int start, int end)
        {
            int i = ell, j = start, k = start;
            end = end - pLength + 1;
            while (j <= end) {
                while (i < pLength && s[i] == s[i + j]) ++i;
                if (i >= pLength) {
                    while (k < ell && s[k] == s[j + k]) ++k;
                    if (k >= ell) return j;
                }
                j += (i - SkipSearchTable[i]);
                if (i == ell) k = k > 0 ? (k - 1) : 0;
                else
                    if (SkipSearchTable[i] <= ell) {
                        k = SkipSearchTable[i] >= 0 ? SkipSearchTable[i] : 0;
                        i = ell;
                    } else {
                        k = ell;
                        i = SkipSearchTable[i];
                    }
            }
            return -1;
        }
    }

    public int Solve(string S)
    {
        if (S.Length < 3) return 0;
        int n = S.Length, ell = 1, scanIdx = 0;
        for (; ell < n && S[ell - 1] == S[ell]; ell++) ;
        if (ell == n) return (n / 3);
        if (ell < n / 3) {
            KMP kmp = new KMP(S);
            scanIdx = (int)Math.Min(n / 3 - 1, kmp.SkipSearchTable[n - 1]);
            if (ell <= scanIdx)
            {
                RabinKarp[] rks = new RabinKarp[] {
                    new RabinKarp(29, 777333111).Initialize(n, scanIdx + 2),
                    new RabinKarp(31, 555111333).Initialize(n, scanIdx + 2)
                };
                RabinKarp.BuildRKParams(S, 0, scanIdx, rks);
                RabinKarp.BuildRKParams(S, n - scanIdx - 2, n-1, rks);
                for (int j = n - scanIdx - 1, idx = -1; scanIdx >= 0; scanIdx--, j++)
                {
                    if (ell > 1 && ell > scanIdx) break;
                    bool skip = false;
                    foreach (RabinKarp rk in rks) {
                        if (rk.RK[scanIdx] != rk[j, n - 1]) {
                            skip = true; break;
                        }
                    }
                    if (skip) continue;

                    idx = kmp.Search(S, (scanIdx == 0 && ell == 1) ? 0 : ell, scanIdx + 1, scanIdx + 1, n - scanIdx - 2);
                    if (idx < 0) continue;
                    if (idx == n) break;
                    if (idx >= 0) return scanIdx + 1;
                }
            }
        }
        if (scanIdx < 0) return 0;

        int ellRight = n, c0 = S[0];
        for (; ellRight > ell && S[ellRight - 1] == c0; ellRight--) ;
        if (n - ellRight <= 0) return 0;

        int min = (int)Math.Min(ell, n - ellRight);
        int ret = (int)Math.Min(min, ((int)Math.Max(ell, n - ellRight)) / 2);
        if (ret >= min) return min;
        scanIdx = ell; ell = -1;
        while (scanIdx < ellRight)
        {
            if (S[scanIdx] == c0) {
                if (ell < 0) ell = scanIdx;
                while (++scanIdx < ellRight && S[scanIdx] == c0) ;
                continue;
            }
            if (ell >= 0) {
                if (ret < scanIdx - ell) {
                    ret = scanIdx - ell;
                    if (ret >= min) return ret;
                }
                ell = -1;
            }
            scanIdx++;
        }
        return (int)Math.Min(min, ell < 0 ? ret : (int)Math.Max(ret, scanIdx - ell));
    }
}