Cod sursa(job #3333350)

Utilizator Bucur_LauraBucur Laura Bucur_Laura Data 13 ianuarie 2026 10:30:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int MAXN = 2000010;

string pattern, text;
int prefixFunction[MAXN];
int occurrences[MAXN];

int patternLength, textLength;
int totalOccurrences = 0;

void buildPrefixFunction()
{
    int i = 1;
    int length = 0;

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

void findPattern()
{
    int i = 0;
    int j = 0;

    while (i < textLength)
    {
        if (text[i] == pattern[j])
        {
            i++;
            j++;

            if (j == patternLength)
            {
                occurrences[++totalOccurrences] = i - j;
                j = prefixFunction[j - 1];
            }
        }
        else
        {
            if (j != 0)
                j = prefixFunction[j - 1];
            else
                i++;
        }
    }

    fout << totalOccurrences << "\n";

    if (totalOccurrences > 1000)
        totalOccurrences = 1000;

    for (int i = 1; i <= totalOccurrences; i++)
        fout << occurrences[i] << " ";
}

int main()
{
    fin >> pattern;
    fin >> text;

    patternLength = pattern.size();
    textLength = text.size();

    buildPrefixFunction();
    findPattern();

    return 0;
}