Cod sursa(job #2591483)

Utilizator popoviciAna16Popovici Ana popoviciAna16 Data 30 martie 2020 17:13:06
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <string>
using namespace std;

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

string s, w;

//folosim algoritmul KMP
int t[2000001], n, m;
//t[i] = lungimea celui mai lung prefix al lui w, astfel incat acesta sa fie sufix al lui a[0...i]; t[i] != i (adica nu pot avea prefix = sufix)

void precalc()
{
    t[0] = 0;
    int k = -1, i;
    for (i = 1; i<w.size(); i++)
    {
        while (k > 0 && w[k+1] != w[i])
            k = t[k];
        if (w[k+1] == w[i])
            k++;
        t[i] = k;
    }
}

int ap[1001];

int main()
{
    fin >> w >> s;
    int i, k = -1;
    for (i = 0; i<s.size(); i++)
    {
        while (k > 0 && s[i] != w[k+1])
            k = t[k]; //adica imi misca w si imi incearca toate deplasamentele posibile
        if (s[i] == w[k+1])
            k++;
        if (k+1 == w.size())
        {
            ap[0]++;
            if (ap[0] <= 1000)
                ap[ap[0]] = i-k;
            k = t[k];
        }
    }
    fout << ap[0] << '\n';
    for (i = 1; i<=min(ap[0], 1000); i++)
        fout << ap[i] << ' ';
    return 0;
}