Cod sursa(job #2590453)

Utilizator ionutomutiuIonut Tomutiu ionutomutiu Data 27 martie 2020 23:21:12
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 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 = 0;
    int j = 1;
    int n = N.size ();
    while (j < n)
    {
        if (N[i] != N[j])
            i = 0;
        if (N[i] != N[j])
        {
            v[j] = 0;
            j++;
        }
        else
        {
            v[j] = i + 1;
            j++;
            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] << " ";
}