Лабораторна робота №3

Умова

Написати пошук підрядка в рядку, використовуючи алгоритми:

Прямий пошук
Алгоритм Кнута, Морриса і Пратта

Аналіз

Обидва алгоритми доволі поширені, тож не має проблеми зробити їх. Прямий пошук це просто 2 цикли, що перевіряють всі символи. Алгоритм Кнута, Морриса і Пратта буде швидшим для великих срок, бо він надає можливість пропускати символи, що вже співпадають.

Структура основних вхідних та вихідних даних

Два рядки:

рядок, в якому шукаємо
рядок, який шукаємо

Алгоритм розв'язання задачі

Так як алгоритми доволі відомі, то я спитаю якийсь AI, щоб він написав мені функції. Далі перевірю, чи вони роблять те, що мають. А також зміню функції в деяких місцях, якщо знайду краще рішення. Протестуємо на різних строках, особливо цікаво порівняти час.

Текст програми

Program.cs

using System.Diagnostics;

Console.WriteLine("Enter a string in which we will search (long one):");
var source = Console.ReadLine();

Console.WriteLine("Enter a string we need to search in previous string (short one)");
var search = Console.ReadLine();

if (source == null || search == null)
{
    Console.WriteLine("Input is invalid. Goodbye");
    return;
}
Console.WriteLine();

Console.WriteLine("Spead test all methods for inputed string");
SpeadTestAll(source, search);

var bigStr = GenerateBigString("roman");
Console.WriteLine("Big str:");
Console.WriteLine($"{bigStr}");
Console.WriteLine("Spead test all methods for big string with similar parts");
SpeadTestAll(bigStr, "roman");

Console.WriteLine("Spead test all methods for big string with not existing substring");
SpeadTestAll(bigStr, "ramadan");

static void SpeadTestAll(string source, string pattern)
{
    List<(string, Func<string, string, int>)> searches = [
        ("Straight", StraightSearch),
        ("KMP", KmpSearch),
        ("Built-in", BuiltInSearch)
    ];

    const int warmup = 100;

    for (int i = 0; i <= warmup; i++)
    {
        if (i == warmup)
        {
            Console.ForegroundColor = ConsoleColor.Red;
        }

        foreach (var (name, func) in searches)
        {
            SpeedTestSearch(name, func, source, pattern);
        }
        Console.WriteLine();

        if (i == warmup)
        {
            Console.ForegroundColor = ConsoleColor.White;
        }
    }
}

static void SpeedTestSearch(string name, Func<string, string, int> search, string source, string pattern)
{
    var stopwatch = new Stopwatch();
    stopwatch.Start();
    var index = search(source, pattern);
    stopwatch.Stop();
    Console.WriteLine($"{name} search found index in: {stopwatch.ElapsedTicks} ticks");
}

static string GenerateBigString(string pattern)
{
    var str = "";
    var piece = pattern[..3];
    for (int i = 0; i < 100000; i++)
    {
        str += piece;
    }
    str += pattern;
    return str;
}

static int BuiltInSearch(string source, string pattern)
{
    return source.IndexOf(pattern);
}

static int StraightSearch(string text, string pattern)
{
    for (int i = 0; i <= text.Length - pattern.Length; i++)
    {
        int j;
        for (j = 0; j < pattern.Length; j++)
        {
            if (text[i + j] != pattern[j])
            {
                break;
            }
        }

        if (j == pattern.Length)
        {
            return i;
        }
    }

    return -1;
}

static int[] ComputePrefixArray(string pattern)
{
    int[] lps = new int[pattern.Length];
    int length = 0;
    int i = 1;

    while (i < pattern.Length)
    {
        if (pattern[i] == pattern[length])
        {
            length += 1;
            lps[i] = length;
            i += 1;
        }
        else if (length != 0)
        {
            length = lps[length - 1];
        }
        else
        {
            lps[i] = 0;
            i += 1;
        }
    }

    return lps;
}

static int KmpSearch(string text, string pattern)
{
    var prefixArray = ComputePrefixArray(pattern);
    int i = 0;
    int j = 0;

    while (i < text.Length)
    {
        if (pattern[j] == text[i])
        {
            i += 1;
            j += 1;
        }

        if (j == pattern.Length)
        {
            return i - j;
        }
        else if (i < text.Length && pattern[j] != text[i])
        {
            if (j != 0)
            {
                j = prefixArray[j - 1];
            }
            else
            {
                i += 1;
            }
        }
    }

    return -1;
}

using System.Diagnostics;

Console.WriteLine("Enter a string in which we will search (long one):");
var source = Console.ReadLine();

Console.WriteLine("Enter a string we need to search in previous string (short one)");
var search = Console.ReadLine();

if (source == null || search == null)
{
    Console.WriteLine("Input is invalid. Goodbye");
    return;
}
Console.WriteLine();

Console.WriteLine("Spead test all methods for inputed string");
SpeadTestAll(source, search);

var bigStr = GenerateBigString("roman");
Console.WriteLine("Big str:");
Console.WriteLine($"{bigStr}");
Console.WriteLine("Spead test all methods for big string with similar parts");
SpeadTestAll(bigStr, "roman");

Console.WriteLine("Spead test all methods for big string with not existing substring");
SpeadTestAll(bigStr, "ramadan");

static void SpeadTestAll(string source, string pattern)
{
    List<(string, Func<string, string, int>)> searches = [
        ("Straight", StraightSearch),
        ("KMP", KmpSearch),
        ("Built-in", BuiltInSearch)
    ];

    const int warmup = 100;

    for (int i = 0; i <= warmup; i++)
    {
        if (i == warmup)
        {
            Console.ForegroundColor = ConsoleColor.Red;
        }

        foreach (var (name, func) in searches)
        {
            SpeedTestSearch(name, func, source, pattern);
        }
        Console.WriteLine();

        if (i == warmup)
        {
            Console.ForegroundColor = ConsoleColor.White;
        }
    }
}

static void SpeedTestSearch(string name, Func<string, string, int> search, string source, string pattern)
{
    var stopwatch = new Stopwatch();
    stopwatch.Start();
    var index = search(source, pattern);
    stopwatch.Stop();
    Console.WriteLine($"{name} search found index in: {stopwatch.ElapsedTicks} ticks");
}

static string GenerateBigString(string pattern)
{
    var str = "";
    var piece = pattern[..3];
    for (int i = 0; i < 100000; i++)
    {
        str += piece;
    }
    str += pattern;
    return str;
}

static int BuiltInSearch(string source, string pattern)
{
    return source.IndexOf(pattern);
}

static int StraightSearch(string text, string pattern)
{
    for (int i = 0; i <= text.Length - pattern.Length; i++)
    {
        int j;
        for (j = 0; j < pattern.Length; j++)
        {
            if (text[i + j] != pattern[j])
            {
                break;
            }
        }

        if (j == pattern.Length)
        {
            return i;
        }
    }

    return -1;
}

static int[] ComputePrefixArray(string pattern)
{
    int[] lps = new int[pattern.Length];
    int length = 0;
    int i = 1;

    while (i < pattern.Length)
    {
        if (pattern[i] == pattern[length])
        {
            length += 1;
            lps[i] = length;
            i += 1;
        }
        else if (length != 0)
        {
            length = lps[length - 1];
        }
        else
        {
            lps[i] = 0;
            i += 1;
        }
    }

    return lps;
}

static int KmpSearch(string text, string pattern)
{
    var prefixArray = ComputePrefixArray(pattern);
    int i = 0;
    int j = 0;

    while (i < text.Length)
    {
        if (pattern[j] == text[i])
        {
            i += 1;
            j += 1;
        }

        if (j == pattern.Length)
        {
            return i - j;
        }
        else if (i < text.Length && pattern[j] != text[i])
        {
            if (j != 0)
            {
                j = prefixArray[j - 1];
            }
            else
            {
                i += 1;
            }
        }
    }

    return -1;
}

Результати тестування програми та аналіз отриманих помилок

В результаті побічимо, що на невеликих строках прямий пошук швидший, або має такуж швідкість як Кнута, Морриса і Пратта.

На великих строках із повтореннями частки підстроки алгоритм Кнута, Морриса і Пратта показує результати краще в 1.5 рази ніж прямий алгоритм.

На великих строках при пошуку неіснуючої підстроки алгоритм Кнута, Морриса і Пратта показує гірші результати, або схожі з прямим алгоритмом. Це напевно через те, що нам все ожно треба перебирати всю строку й в ній занадно мало зхожих з підстрокою частин.

Вбудована функція IndexOf набагато швидша за прямий пошук та алгоритм Кнута, Морриса і Пратта. Тільки на дуже малиш строках мої функції були швидші. Скоріш за все вбудована функція має багато оптимізацій та швидші алгоритми під капотом. Бо результати на велики рядках відрізнялись в 5-6 раз.

Лабораторна робота №3 ​

Умова ​

Аналіз ​

Структура основних вхідних та вихідних даних ​

Алгоритм розв'язання задачі ​

Текст програми ​

Результати тестування програми та аналіз отриманих помилок ​