Cod sursa(job #2909800)

Utilizator vmnechitaNechita Vlad-Mihai vmnechita Data 15 iunie 2022 21:21:40
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pf push_front
#define MOD 1000000007
#define MAX 2000005

using namespace std;

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

int main()
{
    vector < int > raspuns;
    string s1, s2;
    int n, m, i, k, p[MAX+MAX];

    fin >> s1 >> s2, n = s1.size(), m = s2.size();
    if(n > m) fout << 0;
    else
    {
        s1 += '#';
        s1 += s2;

        p[0] = -1;
        for(i = 1; i <= n + m + 1; i++)
        {
            k = p[i-1];
            while(k >= 0 && s1[k] != s1[i-1]) k = p[k];
            p[i] = k + 1;

            if(p[i] == n) raspuns.pb(i - n - n - 1);
        }

        if(raspuns.size() <= 1000)
        {
            fout << raspuns.size() << '\n';
            for(auto it:raspuns) fout << it << ' ';
        }
        else
        {
            fout << raspuns.size() << '\n';
            for(i = 0; i < 1000; i++) fout << raspuns[i] << ' ';
        }
    }


    return 0;
}