Cod sursa(job #2451271)

Utilizator StanCatalinStanCatalin StanCatalin Data 26 august 2019 12:49:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int dim = 2000005;

string a,b;
int kmp[dim],sol[dim],cnt = 0;

int Rezolva()
{
    int act = 0,rez = 0,n = a.length();
    for (int i=1; i<n; i++)
    {
        while (act != 0 && a[i] != a[act])
        {
            act = kmp[act-1];
        }
        if (a[i] == a[act])
        {
            act++;
        }
        kmp[i] = act;
    }
    act = 0;
    for (int i=0; i<b.length(); i++)
    {
        while (act != 0 && b[i] != a[act])
        {
            act = kmp[act-1];
        }
        if (b[i] == a[act])
        {
            act++;
        }
        if (act == a.length())
        {
            cnt++;
            if (cnt <= 1000)
            {
                sol[cnt-1] = i-act+1;
            }
            act = kmp[act-1];
        }
    }
}

int main()
{
    in >> a >> b;
    Rezolva();
    out << cnt << "\n";
    cnt = min(cnt,1000);
    for (int i = 0; i < cnt; i++)
    {
        out << sol[i] << " ";
    }
    return 0;
}