Cod sursa(job #2345947)

Utilizator AlexandruGabrielAliciuc Alexandru AlexandruGabriel Data 16 februarie 2019 21:20:20
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>

using namespace std;

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

string sir, model;
vector <int> urm, ans;
int n, m;

void Prefix()
{
    int i = 1, j = 0;
    urm.push_back(0);
    while (i < m)
    {
        if (model[i] == model[j])
        {
            j++;
            urm.push_back(j);
            i++;
        }
        else
        {
           if (j > 0)
            j = urm[j - 1];
           else
           {
               urm.push_back(0);
               i++;
           }
        }
    }
}

void KMP()
{
    int i = 0, j = 0;
    while (i < n)
    {
        if (sir[i] == model[j])
        {
            i++;
            j++;
        }
        if (j == m)
        {
            ans.push_back(i - j);
            j = urm[j - 1];
        }
        if (i < n && sir[i] != model[j])
        {
            if (j > 0)
                j = urm[j - 1];
            else
                i++;
        }
    }
}

int main()
{
    fin >> model >> sir;
    n = sir.size();
    m = model.size();
    Prefix();
    KMP();
    fout << ans.size() << "\n";
    for (int i = 0; i < (ans.size() > 1000 ? 1000 : ans.size()); i++)
        fout << ans[i] << " ";
    return 0;
}