Cod sursa(job #2590479)

Utilizator ionutomutiuIonut Tomutiu ionutomutiu Data 28 martie 2020 01:27:39
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
using namespace std;
int v[2000000];
vector <int> sol;
int cnt;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
void strstr (string N, string M)
{
    int i;
    int j = 0;
    int n = N.size ();
    for (i = 1; i < n;)
    {
        if (N[i] == N[j])
        {
            j++;
            v[i] = j;
            i++;
        }
        else
        {
            if (j != 0)
                j = v[j - 1];
            else
            {
                v[i] = 0;
                i++;
            }
        }


    }
    i = 0;
    j = 0;
    int m = M.size ();
    while (i < m)
    {
        if (N[j] == M[i])
        {
            i++;
            j++;
        }
        else
        {
            if (j != 0)
                j = v[j - 1];
            if (N[j] == M[i])
            {
                i++;
                j++;
            }
            else
                i++;
        }
        if (j == n)
            sol.push_back (i - n), cnt++;
    }
}
int main ()
{
    string n, m;
    fin >> n;
    fin >> m;
    strstr (n, m);
    fout << cnt << "\n";
    for (int i = 0; i < sol.size () && i <= 999; i++)
        fout << sol[i] << " ";
}