Cod sursa(job #2983465)

Utilizator BeneIonut2208Bene Ionut-Matei BeneIonut2208 Data 22 februarie 2023 15:08:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>

using namespace std;

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

string A, B;
int k, poz[2000005];

int lps[2000005];

void generare_lps()
{
    int n = A.size();
    int j = 0;
    for(int i = 1; i < n; i++)
    {
        while(j > 0 && A[j] != A[i])
            j = lps[j - 1];
        if(A[j] == A[i])
            j++;
        lps[i] = j;
    }
}

void KMP()
{
    generare_lps();
    int n = B.size();
    int m = A.size();
    int j = 0;
    for(int i = 0; i < n; i++)
    {
        while(j > 0 && A[j] != B[i])
            j = lps[j - 1];
        if(A[j] == B[i])
            j++;
        if(j == m)
        {
            poz[k++] = i - m + 1;
            j = lps[j - 1];
        }

    }
}

int main()
{
    fin >> A >> B;
    KMP();
    fout << k << '\n';
    if(k <= 1000)
    {
        for(int i = 0; i < k; i++)
            fout << poz[i] << ' ';
    }
    else
    {
        for(int i = 0; i < 1000; i++)
            fout << poz[i] << ' ';
    }
    return 0;
}