ロリハ計測.cs

using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;

using BenchmarkDotNet.Running;
using BenchmarkDotNet.Attributes;

public static class P
{
    public static void Main()
    {
        BenchmarkRunner.Run<RollingHashBenchMark>();   
    }
}

public class RollingHashBenchMark
{
    readonly int n;
    readonly string s;
    public RollingHashBenchMark()
    {
        var rng = new Random();
        n = 10000;
        s = string.Join("", Enumerable.Range(0, n).Select(_ => rng.Next('a', 'z')));
    }
    [Benchmark]
    public void MersennePrimeMod()
    {
        int curMaxLength = 0;
        var hash = new MersennePrimeModRollingHash(s);
        for (int i = 0; i < s.Length; i++)
            for (int j = i; j < s.Length; j++)
                while (curMaxLength < j - i && j + curMaxLength < n && hash.Slice(i, curMaxLength + 1) == hash.Slice(j, curMaxLength + 1)) curMaxLength++;
    }
    [Benchmark]
    public void SingleMod()
    {
        int curMaxLength = 0;
        var hash = new SingleInt32ModRollingHash(s);
        for (int i = 0; i < s.Length; i++)
            for (int j = i; j < s.Length; j++)
                while (curMaxLength < j - i && j + curMaxLength < n && hash.Slice(i, curMaxLength + 1) == hash.Slice(j, curMaxLength + 1)) curMaxLength++;
    }
    [Benchmark]
    public void DoubleMod()
    {
        int curMaxLength = 0;
        var hash = new DoubleInt32ModRollingHash(s);
        for (int i = 0; i < s.Length; i++)
            for (int j = i; j < s.Length; j++)
                while (curMaxLength < j - i && j + curMaxLength < n && hash.Slice(i, curMaxLength + 1) == hash.Slice(j, curMaxLength + 1)) curMaxLength++;

    }
}

class SingleInt32ModRollingHash
{
    const ulong MOD = 1000000007;
    const ulong POSITIVIZER = MOD << 31;
    static uint Base;
    static ulong[] powMemo = new ulong[500000 + 1];

    static SingleInt32ModRollingHash()
    {
        Base = (uint)new Random().Next(129, int.MaxValue);
        powMemo[0] = 1;
        for (int i = 1; i < powMemo.Length; i++)
            powMemo[i] = (powMemo[i - 1] * Base) % MOD;
    }

    ulong[] hash;

    public SingleInt32ModRollingHash(string s)
    {
        hash = new ulong[s.Length + 1];
        for (int i = 0; i < s.Length; i++)
            hash[i + 1] = (hash[i] * Base + s[i]) % MOD;
    }

    public ulong Slice(int begin, int length)
    {
        return (hash[begin + length] + POSITIVIZER - hash[begin] * powMemo[length]) % MOD;
    }
}

class DoubleInt32ModRollingHash
{
    const ulong MOD1 = 998244353;
    const ulong MOD2 = 1000000007;
    const ulong POSITIVIZER1 = MOD1 << 31;
    const ulong POSITIVIZER2 = MOD2 << 31;
    static uint Base1;
    static uint Base2;
    static ulong[] powMemo1 = new ulong[500000 + 1];
    static ulong[] powMemo2 = new ulong[500000 + 1];

    static DoubleInt32ModRollingHash()
    {
        Base1 = (uint)new Random().Next(129, int.MaxValue);
        powMemo1[0] = 1;
        for (int i = 1; i < powMemo1.Length; i++)
            powMemo1[i] = (powMemo1[i - 1] * Base1) % MOD1;
        Base2 = (uint)new Random().Next(129, int.MaxValue);
        powMemo2[0] = 1;
        for (int i = 1; i < powMemo2.Length; i++)
            powMemo2[i] = (powMemo2[i - 1] * Base2) % MOD2;
    }

    ulong[] hash1;
    ulong[] hash2;

    public DoubleInt32ModRollingHash(string s)
    {
        hash1 = new ulong[s.Length + 1];
        for (int i = 0; i < s.Length; i++)
            hash1[i + 1] = (hash1[i] * Base1 + s[i]) % MOD1;
        hash2 = new ulong[s.Length + 1];
        for (int i = 0; i < s.Length; i++)
            hash2[i + 1] = (hash2[i] * Base2 + s[i]) % MOD2;
    }

    public ulong Slice(int begin, int length)
    {
        return 
            ((hash1[begin + length] + POSITIVIZER1 - hash1[begin] * powMemo1[length]) % MOD1) << 32 |
            ((hash2[begin + length] + POSITIVIZER2 - hash2[begin] * powMemo2[length]) % MOD2);
    }
}

class MersennePrimeModRollingHash
{
    const ulong MASK30 = (1UL << 30) - 1;
    const ulong MASK31 = (1UL << 31) - 1;
    const ulong MOD = (1UL << 61) - 1;
    const ulong POSITIVIZER = MOD * ((1UL << 3) - 1);
    static uint Base;
    static ulong[] powMemo = new ulong[500000 + 1];
    static MersennePrimeModRollingHash()
    {
        Base = (uint)new Random().Next(129, int.MaxValue);
        powMemo[0] = 1;
        for (int i = 1; i < powMemo.Length; i++)
            powMemo[i] = CalcMod(Mul(powMemo[i - 1], Base));
    }

    ulong[] hash;

    public MersennePrimeModRollingHash(string s)
    {
        hash = new ulong[s.Length + 1];
        for (int i = 0; i < s.Length; i++)
            hash[i + 1] = CalcMod(Mul(hash[i], Base) + s[i]);
    }

    public ulong Slice(int begin, int length)
    {
        return CalcMod(hash[begin + length] + POSITIVIZER - Mul(hash[begin], powMemo[length]));
    }

    private static ulong Mul(ulong l, ulong r)
    {
        var lu = l >> 31;
        var ld = l & MASK31;
        var ru = r >> 31;
        var rd = r & MASK31;
        var middleBit = ld * ru + lu * rd;
        return ((lu * ru) << 1) +
            ld * rd +
            ((middleBit & MASK30) << 31) +
            (middleBit >> 30);
    }

    private static ulong CalcMod(ulong val)
    {
        if (val <= MOD) return val;
        val = (val & MOD) + (val >> 61);
        if (val > MOD) val -= MOD;
        return val;
    }
}