Cod sursa(job #3291966)

Utilizator SergiuS3003Sergiu Stancu Nicolae SergiuS3003 Data 6 aprilie 2025 15:06:59
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int NMAX = 2000001;
int kmp[NMAX * 2];
char s[NMAX * 2];

void KMP(int lgPattern)
{
    kmp[1] = 0;
    vector<int> pos;
    int counter = 0;
    for (int i = 2; i < strlen(s + 1); i++)
    {
        int k = kmp[i - 1];
        while (k != 0 && s[k + 1] != s[i])
        {
            k = kmp[k];
        }
        if (s[k + 1] == s[i])
        {
            kmp[i] = k + 1;
        }
        if (kmp[i] == lgPattern)
        {
            counter++;
            if (counter <= 1000)
            {
                pos.push_back(i - 2 * lgPattern - 1);
            }
        }
    }
    g << counter << '\n';
    for (auto p: pos)
    {
        g << p << ' ';
    }
}

int main()
{
    f >> (s + 1);
    int lgPattern = strlen(s + 1);
    s[lgPattern + 1] = '#';
    f >> (s + lgPattern + 2);
    KMP(lgPattern);
    return 0;
}