Cod sursa(job #2709316)

Utilizator MattiaMattia Iojica Mattia Data 20 februarie 2021 10:19:23
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>
#define ull long long
#define nmax 2000005
#define bmax 10000
#define mod 1000000007
#define ui unsigned int

using namespace std;


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

char a[nmax], b[nmax];
int n, m;
int urm[nmax];
vector<int>v;

void urmat(char *p)
{
    int k = -1;
    urm[0] = 0;

    for(int x = 1; x < m; x++)
    {
        while(k > 0 && p[k + 1] != p[x])
            k = urm[k];

        if(p[k + 1] == p[x])
            k++;

        urm[x] = k;
    }

}


int main()
{
    int x = -1, cnt = 0;
    f >> b;
    f >> a;

    n = strlen(a);
    m = strlen(b);

    urmat(b);

   /* for(int i = 1; i < m; i++)
        cout << urm[i] << " ";*/


    for(int i = 0; i < n; i++)
    {
        while(x > 0 && b[x + 1] != a[i])
            x = urm[x];

        if(b[x + 1] == a[i])
            x++;


        if(x == m - 1)
        {
            cnt++;
            if(cnt <= 1000)
                v.push_back(i - m + 1);
            //cout << i - m + 1 << ' ';
            x = urm[x];
        }
    }

    g << cnt << '\n';

    for(int i = 0; i< v.size(); i++)
        g << v[i] << " ";

    return 0;
}