Кнут Моррис Пратт

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <stdlib.h>

using namespace std;

// Массив граней
int* bordersArray = nullptr;

// Поиск максимальной грани для подстроки
int findBorder(string input, int index, char newChar)
{
    if (index == 0) // подстрока из одного элемента не имеет собственных граней
        return 0;
    int lastBorderLength = bordersArray[index - 1]; // длина максимальной грани предыдущей подстроки

    if (input[lastBorderLength] == newChar) // если символ совпал с последним, то грань увеличилась на 1
        return lastBorderLength + 1;
    else if (lastBorderLength == 0) // если последняя грань была нулевой, то ничего не изменилось
        return 0;
    else
        return findBorder(input, lastBorderLength, newChar); // ищем подстроку, в которой символ будет входить в грань
}

// Построение граней
void buildBordersArray(string input)
{
    if (bordersArray == nullptr)
        bordersArray = new int[input.length()];

    for (int i = 0; i < input.length(); ++i)
        bordersArray[i] = findBorder(input, i, input[i]);
}
// Поиск подстроки p в строке t
vector<int> getSubstrings(string t, string p)
{
    if (bordersArray == nullptr)
        bordersArray = new int[p.length()];
    // Строим масссив граней для подстроки
    buildBordersArray(p);

    vector<int> occurences;
    int count = 0; // счетчик количества совпавших элементов

    for (int i = 0; i < t.length(); ++i)
    {
        if (p[count] == t[i]) // если символы совпали, увеличиваем счетчик
            count +=1;
        else // иначе пытаемся понять, сколько символов уже совпало - оно равно количеству граней
            count = findBorder(p, count, t[i]);

        if (count == p.length()) // если количество совпавших символов равно длине подстроки
        {
            occurences.push_back(i + 1 - count); // добавляем вхождение
            count = bordersArray[count - 1]; // ищем, сколько элементов уже совпало в гранях подстроки
        }
    }
    return occurences;
}

int main()
{
    string t;
    string p;
    vector<int> res;

    ifstream fin;
    fin.open("input.txt");
    if (fin.is_open())
    {
        getline(fin, t);
        getline(fin, p);
        fin.close();
    }

    res = getSubstrings(t, p);

    fstream fout;
    fout.open("output.txt", ios::out);
    fout << res.size() << "\n";
    for (std::vector<int>::const_iterator i = res.begin(); i != res.end(); ++i)
        fout << *i << "\n";
    fout.close();

    return 0;
}